2023

Exact computations with quasiseparable matrices

Pernet, Clément, Signargout, Hippolyte, Villard, Gilles

Understand

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.

Built on

On the Numerical Solution of One-Dimensional Integral and Differential Equations
H.P. Starr. 1992 · 1992
Earlier work this paper cites.
On a new class of structured matrices
Y. Eidelman and I. Gohberg. 1999 · 1999
Earlier work this paper cites.
A Sparse Matrix Arithmetic Based on H-Matrices. Part I: Introduction to H-Matrices
W. Hackbusch. 1999 · 1999
Earlier work this paper cites.
On H2-Matrices. In Lectures on Applied Mathematics . Springer Berlin Heidelberg, 9–29
W. Hackbusch, B. Khoromskij, and S. A. Sauter. 2000 · 2000
Earlier work this paper cites.
Algorithms for Matrix Canonical Forms
A. Storjohann. 2000 · 2000
Earlier work this paper cites.
Fast Stable Solver for Sequentially Semi-separable Linear Systems of Equations. In High Performance Computing — HiPC 2002 . Springer Berlin Heidelberg, 545–554
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, and A. J. van der Veen. 2002 · 2002
Earlier work this paper cites.
Fast and Stable Algorithms for Banded Plus Semiseparable Systems of Linear Equations
S. Chandrasekaran and M. Gu. 2003 · 2003
Earlier work this paper cites.
Some Fast Algorithms for Sequentially Semiseparable Representations
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, A. J. van der Veen, and D. White. 2005 · 2005
Earlier work this paper cites.
On generators of quasiseparable finite block matrices
Y. Eidelman and I. Gohberg. 2005 · 2005
Earlier work this paper cites.

Similar

Fast algorithms with applications to PDEs
W. Lyons. 2005 · 2005
Cited alongside, same era.
A bibliography on semiseparable matrices*
R. Vandebril, M. Van Barel, G.H. Golub, and N. Mastronardi. 2005 · 2005
Cited alongside, same era.
A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
S. Chandrasekaran, M. Gu, and T. Pals. 2006 · 2006
Cited alongside, same era.
Bruhat canonical form for linear systems
W. Manthey and U. Helmke. 2007 · 2007
Cited alongside, same era.
Algorithms to Solve Hierarchically Semi-separable Systems . Vol. 176
Z. Sheng, P. Dewilde, and S. Chandrasekaran. 2007 · 2007
Cited alongside, same era.
A Givens-Weight Representation for Rank Structured Matrices
Steven Delvaux and Marc Van Barel. 2008 · 2008
Cited alongside, same era.
Matrix Computations and Semiseparable Matrices: Linear Systems
R. Vandebril, M. Van Barel, Gene H. Golub, and N. Mastronardi. 2008 · 2008
Cited alongside, same era.
Fast algorithms for hierarchically semiseparable matrices
J. Xia, S. Chandrasekaran, M. Gu, and X.S. Li. 2010 · 2010
Cited alongside, same era.
A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
P.G. Martinsson. 2011 · 2011
Cited alongside, same era.

Then

Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
C.-P. Jeannerod, C. Pernet, and A. Storjohann. 2013 · 2013
Later among the works it cites.
Implicit QR for rank-structured matrix pencils
P. Boito, Y. Eidelman, and L. Gemignani. 2014 · 2014
Later among the works it cites.
Hierarchical Matrices: Algorithms and Analysis . Vol. 49
W. Hackbusch. 2015 · 2015
Later among the works it cites.
Fast computation of the rank profile matrix and the generalized Bruhat decomposition
J.-G. Dumas, C. Pernet, and Z. Sultan. 2017 · 2016
Later among the works it cites.
Computing with Quasiseparable Matrices. In Proc. ISSAC (Waterloo, ON, Canada). ACM Press, 389–396
Clément Pernet. 2016 · 2016
Later among the works it cites.
A real QZ algorithm for structured companion pencils
P. Boito, Y. Eidelman, and L. Gemignani. 2017 · 2017
Later among the works it cites.
Time and space efficient generators for quasiseparable matrices
C. Pernet and A. Storjohann. 2018 · 2017
Later among the works it cites.
FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package (v2.5.0 ed.)
The FFLAS-FFPACK group. 2021 · 2021
Later among the works it cites.
Leading constants of rank deficient Gaussian elimination
C. Pernet, H. Signargout, and G. Villard. 2023 · 2023
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…