On matrices with displacement structure: generalized operators and faster algorithms

DOI10.1137/16M1062855MaRDI QIDQ5348227zbMATH OpenOpenAlexFDO

Authors Alin Bostan, Claude-Pierre Jeannerod, Christophe Mouilleron, Éric Schost

Publication date 14 August 2017

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityalgorithminversionmatrix multiplicationLas Vegas algorithmslinear system solvingdisplacement rankstructured linear algebra

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Complexity and performance of numerical algorithms (65Y20)

Abstract: For matrices with displacement structure, basic operations like multiplication, inversion, and linear system solving can all be expressed in terms of the following task: evaluate the product $mathsfAmathsfB$, where $mathsfA$ is a structured $nimesn$ matrix of displacement rank $alpha$, and $mathsfB$ is an arbitrary $nimesalpha$ matrix. Given $mathsfB$ and a so-called "generator" of $mathsfA$, this product is classically computed with a cost ranging from $O(alph{a}^{2}mathscrM(n))$ to $O(alph{a}^{2}mathscrM(n)log(n))$ arithmetic operations, depending on the type of structure of $mathsfA$; here, $mathscrM$ is a cost function for polynomial multiplication. In this paper, we first generalize classical displacement operators, based on block diagonal matrices with companion diagonal blocks, and then design fast algorithms to perform the task above for this extended class of structured matrices. The cost of these algorithms ranges from $O(alph{a}^{omega-1}mathscrM(n))$ to $O(alph{a}^{omega-1}mathscrM(n)log(n))$, with $omega$ such that two $nimesn$ matrices over a field can be multiplied using $O(n^{o}mega)$ field operations. By combining this result with classical randomized regularization techniques, we obtain faster Las Vegas algorithms for structured inversion and linear system solving.

Recommendations

• A two-pronged progress in structured dense matrix vector multiplication
• Solving structured linear systems with large displacement rank
• Iterative inversion of structured matrices
• Inversion of Displacement Operators
• Publication:4952723

Cites work

• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• scientific article; zbMATH DE number 3889718 (Why is no real title available?)
• scientific article; zbMATH DE number 177858 (Why is no real title available?)
• scientific article; zbMATH DE number 1263429 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• scientific article; zbMATH DE number 1445400 (Why is no real title available?)
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• Complexity issues in bivariate polynomial factorization
• Complexity of multiplication with vectors for structured matrices
• Computing specified generators of structured matrix inverses
• Displacement ranks of a matrix
• Displacement ranks of matrices and linear equations
• Evaluating Polynomials at Fixed Sets of Points
• Fast algorithms for elementary operations on complex power series
• Fast algorithms with preprocessing for matrix-vector multiplication problems
• Fast multiplication of large numbers
• Fast multiplication of polynomials over fields of characteristic 2
• Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations
• Gaussian elimination is not optimal
• Inversion of Displacement Operators
• Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation
• Modern computer algebra
• New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices
• On Computations with Dense Structured Matrices
• Polynomial evaluation and interpolation on special sets of points
• Powers of tensors and fast matrix multiplication
• Solving structured linear systems with large displacement rank
• Superfast algorithms for Cauchy-like matrix computations and extensions
• The middle product algorithm. I: Speeding up the division and square root of power series
• Transformations of matrix structures work again
• Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication

Cited in

(11)

• scientific article; zbMATH DE number 1136270 (Why is no real title available?)
• Unified nearly optimal algorithms for structured integer matrices
• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• High-order lifting for polynomial Sylvester matrices
• Generalized Displacement Structure for Block-Toeplitz, Toeplitz-Block, and Toeplitz-Derived Matrices
• Subquadratic-time algorithms for normal bases
• A two-pronged progress in structured dense matrix vector multiplication
• Algorithms for simultaneous Hermite-Padé approximations
• scientific article; zbMATH DE number 4215255 (Why is no real title available?)
• The Schur algorithm for matrices with Hessenberg displacement structure
• Computing the characteristic polynomial of generic Toeplitz-like and Hankel-like matrices

This page was built for publication: On matrices with displacement structure: generalized operators and faster algorithms

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