Solving structured linear systems with large displacement rank
From MaRDI portal
Publication:954988
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
algorithmsinteger arithmeticdense linear algebraCauchy-like matricesToeplitz-like matricesstructured linear algebraVandermonde-like matrices
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
