Computing with quasiseparable matrices

DOI10.1145/2930889.2930915MaRDI QIDQ2985852zbMATH OpenOpenAlexFDO

Authors Clément Pernet

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.01246

zbMATH Keywords

generalized Bruhat decompositionquasiseparable matricesrank profile

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: The class of quasiseparable matrices is defined by a pair of bounds, called the quasiseparable orders, on the ranks of the maximal sub-matrices entirely located in their strictly lower and upper triangular parts. These arise naturally in applications, as e.g. the inverse of band matrices, and are widely used for they admit structured representations allowing to compute with them in time linear in the dimension and quadratic with the quasiseparable order. We show, in this paper, the connection between the notion of quasisepa-rability and the rank profile matrix invariant, presented in [Dumas & al. ISSAC'15]. This allows us to propose an algorithm computing the quasiseparable orders (rL, rU) in time O(n^2 s^($omega$--2)) where s = max(rL, rU) and $omega$ the exponent of matrix multiplication. We then present two new structured representations, a binary tree of PLUQ decompositions, and the Bruhat generator, using respectively O(ns log n/s) and O(ns) field elements instead of O(ns^2) for the previously known generators. We present algorithms computing these representations in time O(n^2 s^($omega$--2)). These representations allow a matrix-vector product in time linear in the size of their representation. Lastly we show how to multiply two such structured matrices in time O(n^2 s^($omega$--2)).

Recommendations

• Time and space efficient generators for quasiseparable matrices
• On a new class of structured matrices
• Out-of-band quasiseparable matrices
• Nested product decomposition of quasiseparable matrices
• On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms

Cited in

(9)

• On a new class of structured matrices
• Time and space efficient generators for quasiseparable matrices
• Piecewise separable matrices
• LU factorization for matrices in quasiseparable form via orthogonal transformations
• Structured condition numbers for linear systems with parameterized quasiseparable coefficient matrices
• Nested product decomposition of quasiseparable matrices
• Exact computations with quasiseparable matrices
• Representation of quasiseparable matrices using excluded sums and equivalent charges
• Out-of-band quasiseparable matrices

This page was built for publication: Computing with quasiseparable matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985852)