On matrices with displacement structure: generalized operators and faster algorithms

DOI10.1137/16M1062855zbMATH Open1371.65025arXiv1703.03734OpenAlexW2595057318MaRDI QIDQ5348227FDOQ5348227

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)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Title not available (Why is that?)
• Unified nearly optimal algorithms for structured integer matrices
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)