Solving structured linear systems with large displacement rank

DOI10.1016/j.tcs.2008.05.014zbMath1169.65023OpenAlexW1994077047MaRDI QIDQ954988

Éric Schost, Claude-Pierre Jeannerod, Alin Bostan

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.05.014

zbMATH Keywords

algorithmsinteger arithmeticdense linear algebraCauchy-like matricesToeplitz-like matricesstructured linear algebraVandermonde-like matrices

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Linear equations (linear algebraic aspects) (15A06)

Related Items

Computing minimal interpolation bases ⋮ Time and space efficient generators for quasiseparable matrices ⋮ On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms ⋮ Fast Algorithms for Discrete Differential Equations ⋮ Fast coefficient computation for algebraic power series in positive characteristic ⋮ Algorithms for simultaneous Hermite-Padé approximations ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization ⋮ Fast amortized multi-point evaluation ⋮ Power decoding Reed-Solomon codes up to the Johnson radius ⋮ An EM-based iterative method for solving large sparse linear systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The aggregation and cancellation techniques as a practical tool for faster matrix multiplication
• A general module theoretic framework for vector M-Padé and matrix rational interpolation
• Interpolating polynomials from their values
• Matrix multiplication via arithmetic progressions
• Displacement ranks of matrices and linear equations
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• On practical algorithms for accelerated matrix multiplication
• On fast multiplication of polynomials over arbitrary algebras
• A reliable method for computing M-Padé approximants on arbitrary staircases
• Parametrization of Newton's iteration for computations with structured matrices and applications
• A probabilistic remark on algebraic program testing
• Complexity of multiplication with vectors for structured matrices
• On short multiplications and divisions
• An efficient solution for Cauchy-like systems of linear equations
• Ideal basis and primary decompositions: case of two variables
• Polynomial interpolation in several variables
• Superfast algorithms for Cauchy-like matrix computations and extensions
• An inversion formula and fast algorithms for Cauchy-Vandermonde matrices
• Computing Frobenius maps and factoring polynomials
• Gaussian elimination is not optimal
• Fast multiplication of large numbers
• Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs
• Solving sparse rational linear systems
• The Inverses of Block Hankel and Block Toeplitz Matrices
• On Computations with Dense Structured Matrices
• Speeding the Pollard and Elliptic Curve Methods of Factorization
• Greatest common divisors of polynomials given by straight-line programs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A generalization of the fast LUP matrix decomposition algorithm and applications
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Inversion of Displacement Operators
• Factoring into coprimes in essentially linear time
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Algorithms – ESA 2004