2023/02/09 by Clément Pernet, Pernet, Clément, Hippolyte Signargout +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #Matrix Theory and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.2302.04515
openalex publication_date 2023/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quasi-separable matrices are a class of rank-structured matriceswidely used in numerical linear algebra and of growing interestin computer algebra, with applications in e.g. the linearization ofpolynomial matrices. Various representation formats exist for thesematrices that have rarely been compared.We show how the most central formats SSS and HSS can beadapted to symbolic computation, where the exact rank replacesthreshold based numerical ranks. We clarify their links and comparethem with the Bruhat format. To this end, we state their space andtime cost estimates based on fast matrix multiplication, and comparethem, with their leading constants. The comparison is supportedby software experiments.We make further progresses for the Bruhat format, for which wegive a generation algorithm, following a Crout elimination scheme,which specializes into fast algorithms for the construction from asparse matrix or from the sum of Bruhat representations.