Time and space efficient generators for quasiseparable matrices
From MaRDI portal
Publication:2409018
Abstract: The class of quasiseparable matrices is defined by the property that any submatrix entirely below or above the main diagonal has small rank, namely below a bound called the order of quasiseparability. These matrices arise naturally in solving PDE's for particle interaction with the Fast Multi-pole Method (FMM), or computing generalized eigenvalues. From these application fields, structured representations and algorithms have been designed in numerical linear algebra to compute with these matrices in time linear in the matrix dimension and either quadratic or cubic in the quasiseparability order. Motivated by the design of the general purpose exact linear algebra library LinBox, and by algorithmic applications in algebraic computing, we adapt existing techniques introduce novel ones to use quasiseparable matrices in exact linear algebra, where sub-cubic matrix arithmetic is available. In particular, we will show, the connection between the notion of quasiseparability and the rank profile matrix invariant, that we have introduced in 2015. It results in two new structured representations, one being a simpler variation on the hierarchically semiseparable storage, and the second one exploiting the generalized Bruhat decomposition. As a consequence, most basic operations, such as computing the quasiseparability orders, applying a vector, a block vector, multiplying two quasiseparable matrices together, inverting a quasiseparable matrix, can be at least as fast and often faster than previous existing algorithms.
Recommendations
- Efficient generation of random nonsingular matrices
- scientific article; zbMATH DE number 1618010
- On generators of quasiseparable finite block matrices
- Computing with quasiseparable matrices
- Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
- Exact computations with quasiseparable matrices
- scientific article; zbMATH DE number 4024637
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- A parallel QR-factorization/solver of quasiseparable matrices
Cites work
- A bibliography on semiseparable matrices
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- A Givens-Weight Representation for Rank Structured Matrices
- Algorithms to solve hierarchically semi-separable systems
- Bruhat canonical form for linear systems
- Computing the rank profile matrix
- Computing with quasiseparable matrices
- Displacement ranks of matrices and linear equations
- Fast algorithms for hierarchically semiseparable matrices
- Fast generalized Bruhat decomposition
- Gaussian elimination is not optimal
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- Implicit QR for companion-like pencils
- Linear complexity algorithms for semiseparable matrices
- Matrix Bruhat decompositions with a remark on the QR(GR) algorithm
- On a new class of structured matrices
- On Computations with Dense Structured Matrices
- On generators of quasiseparable finite block matrices
- On Rank-Revealing Factorisations
- On the existence and computation of rank-revealing LU factorizations
- Powers of tensors and fast matrix multiplication
- Rang revealing QR factorizations
- Rank revealing \(LU\) factorizations
- Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
- Simultaneous computation of the row and column rank profiles
- Solving structured linear systems with large displacement rank
- Some Fast Algorithms for Sequentially Semiseparable Representations
- Sur les représentations induites des groupes de Lie
- The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order
Cited in
(12)- Separable type representations of matrices and fast algorithms. Volume 1. Basics. Completion problems. Multiplication and inversion algorithms
- Piecewise separable matrices
- Computing with quasiseparable matrices
- scientific article; zbMATH DE number 4024637 (Why is no real title available?)
- Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
- Stability of QR-based fast system solvers for a subclass of quasiseparable rank one matrices
- Nested product decomposition of quasiseparable matrices
- Matrix Structures and Matrix Functions
- Exact computations with quasiseparable matrices
- Representation of quasiseparable matrices using excluded sums and equivalent charges
- On generators of quasiseparable finite block matrices
- Out-of-band quasiseparable matrices
This page was built for publication: Time and space efficient generators for quasiseparable matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409018)
