Solving structured linear systems with large displacement rank
From MaRDI portal
Publication:954988
DOI10.1016/j.tcs.2008.05.014zbMath1169.65023MaRDI 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
algorithms; integer arithmetic; dense linear algebra; Cauchy-like matrices; Toeplitz-like matrices; structured linear algebra; Vandermonde-like matrices
65F05: Direct numerical methods for linear systems and matrix inversion
15A06: Linear equations (linear algebraic aspects)
Cites Work
- 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
- 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