Exact computations with quasiseparable matrices
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 ha...
Published in: | Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation |
---|---|
Main Authors: | , , |
Other Authors: | , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2023
|
Subjects: | |
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 |
id |
ftunivlyon:oai:HAL:hal-03978799v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivlyon:oai:HAL:hal-03978799v1 2024-09-15T18:39:16+00:00 Exact computations with quasiseparable matrices Pernet, Clément Signargout, Hippolyte Villard, Gilles 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) Tromso, Norway 2023-07-17 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 en eng HAL CCSD ACM info:eu-repo/semantics/altIdentifier/arxiv/2302.04515 info:eu-repo/semantics/altIdentifier/doi/10.1145/2930889.2930915 hal-03978799 https://cnrs.hal.science/hal-03978799 https://cnrs.hal.science/hal-03978799/document https://cnrs.hal.science/hal-03978799/file/quasisep.pdf ARXIV: 2302.04515 doi:10.1145/2930889.2930915 info:eu-repo/semantics/OpenAccess ISSAC'23: the 2023 International Symposium on Symbolic and Algebraic Computation https://cnrs.hal.science/hal-03978799 ISSAC'23: the 2023 International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway. pp.480-489, ⟨10.1145/2930889.2930915⟩ Quasiseparable matrix SSS HSS Bruhat generator [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftunivlyon https://doi.org/10.1145/2930889.2930915 2024-07-22T23:38:55Z 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. Conference Object Tromso Tromso Université de Lyon: HAL Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation 389 396 |
institution |
Open Polar |
collection |
Université de Lyon: HAL |
op_collection_id |
ftunivlyon |
language |
English |
topic |
Quasiseparable matrix SSS HSS Bruhat generator [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
spellingShingle |
Quasiseparable matrix SSS HSS Bruhat generator [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Pernet, Clément Signargout, Hippolyte Villard, Gilles Exact computations with quasiseparable matrices |
topic_facet |
Quasiseparable matrix SSS HSS Bruhat generator [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
description |
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. |
author2 |
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 |
author |
Pernet, Clément Signargout, Hippolyte Villard, Gilles |
author_facet |
Pernet, Clément Signargout, Hippolyte Villard, Gilles |
author_sort |
Pernet, Clément |
title |
Exact computations with quasiseparable matrices |
title_short |
Exact computations with quasiseparable matrices |
title_full |
Exact computations with quasiseparable matrices |
title_fullStr |
Exact computations with quasiseparable matrices |
title_full_unstemmed |
Exact computations with quasiseparable matrices |
title_sort |
exact computations with quasiseparable matrices |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
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 |
op_coverage |
Tromso, Norway |
genre |
Tromso Tromso |
genre_facet |
Tromso Tromso |
op_source |
ISSAC'23: the 2023 International Symposium on Symbolic and Algebraic Computation https://cnrs.hal.science/hal-03978799 ISSAC'23: the 2023 International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway. pp.480-489, ⟨10.1145/2930889.2930915⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/arxiv/2302.04515 info:eu-repo/semantics/altIdentifier/doi/10.1145/2930889.2930915 hal-03978799 https://cnrs.hal.science/hal-03978799 https://cnrs.hal.science/hal-03978799/document https://cnrs.hal.science/hal-03978799/file/quasisep.pdf ARXIV: 2302.04515 doi:10.1145/2930889.2930915 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1145/2930889.2930915 |
container_title |
Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation |
container_start_page |
389 |
op_container_end_page |
396 |
_version_ |
1810483662720860160 |