Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization

DOI10.1016/j.camwa.2011.06.006zbMath1231.15004MaRDI QIDQ660795

Pan, Victor Y.

Publication date: 5 February 2012

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.camwa.2011.06.006

zbMATH Keywords

Toeplitz matrices; initialization; iterative refinement; linear systems of equations; Hensel's lifting; Newton's lifting

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

13F20: Polynomial rings and ideals; rings of integer-valued polynomials

15A06: Linear equations (linear algebraic aspects)

15B05: Toeplitz, Cauchy, and related matrices

Related Items

Transformations of matrix structures work again, Iterative Refinement for Linear Programming

Cites Work

• 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
• Algebraic methods for Toeplitz-like matrices and operators
• Matrix multiplication via arithmetic progressions
• Degeneration of structured integer matrices modulo an integer
• Solving structured linear systems with large displacement rank
• Randomized preprocessing of homogeneous linear systems of equations
• Complexity of parallel matrix computations
• Lower bounds for the condition number of Vandermonde matrices
• Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations
• Displacement ranks of matrices and linear equations
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• Exact solution of linear equations using p-adic expansions
• On practical algorithms for accelerated matrix multiplication
• How bad are Hankel matrices?
• Complexity of multiplication with vectors for structured matrices
• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Randomized preprocessing versus pivoting
• Schur aggregation for linear systems and determinants
• Certified dense linear system solving
• A Stabilized Superfast Solver for Nonsymmetric Toeplitz Systems
• An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications
• On Computations with Dense Structured Matrices
• How Can We Speed Up Matrix Multiplication?
• Stability of Methods for Solving Toeplitz Systems of Equations
• Hensel and Newton Methods in Valuation Rings
• Solving sparse linear equations over finite fields
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Acceleration of Euclidean Algorithm and Rational Number Reconstruction
• Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
• Exact solutions to linear systems of equations using output sensitive lifting
• Randomized preconditioning of the MBA algorithm
• Numeric-symbolic exact rational linear system solver