Exact computations with quasiseparable matrices
Pages 480 - 489
Abstract
Quasiseparable matrices are a class of rank-structured matrices widely used in numerical linear algebra and of growing interest in computer algebra, with applications in e.g. the linearization of polynomial matrices. Various representation formats exist for these matrices that have rarely been compared.
We show how the most central formats SSS and HSS can be adapted to symbolic computation, where the exact rank replaces threshold based numerical ranks. We clarify their links and compare them with the Bruhat format. To this end, we state their space and time cost estimates based on fast matrix multiplication, and compare them, with their leading constants. The comparison is supported by software experiments.
We make further progresses for the Bruhat format, for which we give a generation algorithm, following a Crout elimination scheme, which specializes into fast algorithms for the construction from a sparse matrix or from the sum of Bruhat representations.
References
[1]
P. Boito, Y. Eidelman, and L. Gemignani. 2014. Implicit QR for rank-structured matrix pencils. BIT Numerical Mathematics 54, 1 (March 2014), 85–111. https://doi.org/10.1007/s10543-014-0478-0
[2]
P. Boito, Y. Eidelman, and L. Gemignani. 2017. A real QZ algorithm for structured companion pencils. Calcolo 54, 4 (Dec. 2017), 1305–1338. https://doi.org/10.1007/s10092-017-0231-6
[3]
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, A. J. van der Veen, and D. White. 2005. Some Fast Algorithms for Sequentially Semiseparable Representations. SIAM J. Matrix Anal. Appl. 27, 2 (2005), 341–364. https://doi.org/10.1137/S0895479802405884 arXiv:https://doi.org/10.1137/S0895479802405884
[4]
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, and A. J. van der Veen. 2002. Fast Stable Solver for Sequentially Semi-separable Linear Systems of Equations. In High Performance Computing — HiPC 2002. Springer Berlin Heidelberg, 545–554. https://doi.org/10.1007/3-540-36265-7_51
[5]
S. Chandrasekaran and M. Gu. 2003. Fast and Stable Algorithms for Banded Plus Semiseparable Systems of Linear Equations. SIAM J. Matrix Analysis Applications 25 (2003), 373–384. https://doi.org/10.1137/S0895479899353373
[6]
S. Chandrasekaran, M. Gu, and T. Pals. 2006. A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations. SIAM J. Matrix Anal. Appl. 28, 3 (2006), 603–622. https://doi.org/10.1137/S0895479803436652
[7]
Steven Delvaux and Marc Van Barel. 2008. A Givens-Weight Representation for Rank Structured Matrices. SIAM J. Matrix Anal. Appl. 29, 4 (2008), 1147–1170. https://doi.org/10.1137/060654967 _eprint: https://doi.org/10.1137/060654967.
[8]
J.-G. Dumas, C. Pernet, and Z. Sultan. 2017. Fast computation of the rank profile matrix and the generalized Bruhat decomposition. Journal of Symbolic Computation 83 (2017), 187 – 210. https://doi.org/10.1016/j.jsc.2016.11.011
[9]
Y. Eidelman and I. Gohberg. 1999. On a new class of structured matrices. Integral Equations and Operator Theory 34 (1999), 293–324. https://doi.org/10.1007/BF01300581
[10]
Y. Eidelman and I. Gohberg. 2005. On generators of quasiseparable finite block matrices. Calcolo 42 (12 2005), 187–214. https://doi.org/10.1007/s10092-005-0102-4
[11]
The FFLAS-FFPACK group. 2021. FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package (v2.5.0 ed.). http://github.com/linbox-team/fflas-ffpack.
[12]
W. Hackbusch. 1999. A Sparse Matrix Arithmetic Based on H-Matrices. Part I: Introduction to H-Matrices. Computing 62 (1999), 89–108. https://doi.org/10.1007/s006070050015
[13]
W. Hackbusch. 2015. Hierarchical Matrices: Algorithms and Analysis. Vol. 49. Springer. https://doi.org/10.1007/978-3-662-47324-5
[14]
W. Hackbusch, B. Khoromskij, and S. A. Sauter. 2000. On H2-Matrices. In Lectures on Applied Mathematics. Springer Berlin Heidelberg, 9–29. https://doi.org/10.1007/978-3-642-59709-1_2
[15]
C.-P. Jeannerod, C. Pernet, and A. Storjohann. 2013. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. J. Symbolic Comput. 56 (2013), 46–68. https://doi.org/10.1016/j.jsc.2013.04.004
[16]
W. Lyons. 2005. Fast algorithms with applications to PDEs. Ph. D. Dissertation. University of California, Santa Barbara, USA. http://scg.ece.ucsb.edu/publications/theses/Lyons_2005_Thesis.pdf
[17]
W. Manthey and U. Helmke. 2007. Bruhat canonical form for linear systems. Linear Algebra Appl. 425, 2–3 (2007), 261–282. https://doi.org/10.1016/j.laa.2007.01.022
[18]
P.G. Martinsson. 2011. A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix. SIAM J. Matrix Analysis Applications 32 (10 2011), 1251–1274. https://doi.org/10.1137/100786617
[19]
Stefano Massei, Leonardo Robol, and Daniel Kressner. 2020. hm-toolbox: MATLAB software for HODLR and HSS matrices. 42, 2 (2020), C43–C68. https://doi.org/10.1137/19M1288048
[20]
Clément Pernet. 2016. Computing with Quasiseparable Matrices. In Proc. ISSAC (Waterloo, ON, Canada). ACM Press, 389–396. https://doi.org/10.1145/2930889.2930915
[21]
C. Pernet, H. Signargout, and G. Villard. 2023. Leading constants of rank deficient Gaussian elimination. Technical Report. hal:03976168.
[22]
C. Pernet and A. Storjohann. 2018. Time and space efficient generators for quasiseparable matrices. Journal of Symbolic Computation 85 (2018), 224 – 246. https://doi.org/10.1016/j.jsc.2017.07.010
[23]
Z. Sheng, P. Dewilde, and S. Chandrasekaran. 2007. Algorithms to Solve Hierarchically Semi-separable Systems. Vol. 176. 255–294. https://doi.org/10.1007/978-3-7643-8137-0_5
[24]
H.P. Starr. 1992. On the Numerical Solution of One-Dimensional Integral and Differential Equations. Ph. D. Dissertation. Yale University, USA. https://cpsc.yale.edu/sites/default/files/files/tr888.pdf UMI Order No. GAX92-35558.
[25]
A. Storjohann. 2000. Algorithms for Matrix Canonical Forms. Ph. D. Dissertation. Institut für Wissenschaftliches Rechnen, ETH-Zentrum, Zürich, Switzerland. https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/145127/1/eth-24018-01.pdf
[26]
R. Vandebril, M. Van Barel, G.H. Golub, and N. Mastronardi. 2005. A bibliography on semiseparable matrices*. CALCOLO 42 (2005), 249–270. https://doi.org/10.1007/s10092-005-0107-z
[27]
R. Vandebril, M. Van Barel, Gene H. Golub, and N. Mastronardi. 2008. Matrix Computations and Semiseparable Matrices: Linear Systems. Johns Hopkins University Press. https://doi.org/10.1353/book.16537
[28]
J. Xia, S. Chandrasekaran, M. Gu, and X.S. Li. 2010. Fast algorithms for hierarchically semiseparable matrices. Numerical Linear Algebra with Applications 17, 6 (2010), 953–976. https://doi.org/10.1002/nla.691
Recommendations
Nested Product Decomposition of Quasiseparable Matrices
This paper introduces a nested product decomposition of an $n\times n$ quasiseparable matrix $A$. The nested product is formed from small Householder transformations and very sparse matrices with only a few nonzeros isolated to a single column. The ...
Orthogonal Cauchy-like matrices
AbstractCauchy-like matrices arise often as building blocks in decomposition formulas and fast algorithms for various displacement-structured matrices. A complete characterization for orthogonal Cauchy-like matrices is given here. In particular, we show ...
Computations with quasiseparable polynomials and matrices
In this paper, we survey several recent results that highlight an interplay between a relatively new class of quasiseparable matrices and univariate polynomials. Quasiseparable matrices generalize two classical matrix classes, Jacobi (tridiagonal) ...
Comments
Information & Contributors
Information
Published In
July 2023
567 pages
Copyright © 2023 ACM.
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ISSAC 2023
ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023
July 24 - 27, 2023
Tromsø, Norway
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 38Total Downloads
- Downloads (Last 12 months)33
- Downloads (Last 6 weeks)3
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format