Exact computations with quasiseparable matrices

• Published in: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation
• Main Authors: Pernet, Clément, Signargout, Hippolyte, Villard, Gilles
• Other Authors: Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2023
• Subjects: Quasiseparable matrix; SSS; HSS; Bruhat generator; [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]; Norway; Tromso
• Online Access: https://cnrs.hal.science/hal-03978799; https://cnrs.hal.science/hal-03978799/document; https://cnrs.hal.science/hal-03978799/file/quasisep.pdf; https://doi.org/10.1145/2930889.2930915

International audience 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.