Faster inversion and other black box matrix computations using efficient block projections

MaRDI QIDQ5301663zbMATH OpenFDO

Authors Wayne Eberly, Pascal Giorgi, Arne Storjohann, Gilles Villard, Mark Giesbrecht

Publication date 20 January 2009

Mathematics Subject Classification ID

Theory of matrix inversion and generalized inverses (15A09) Computational methods for sparse matrices (65F50) Symbolic computation and algebraic computation (68W30)

Recommendations

• Black box Frobenius decompositions over small fields
• Black box methods for least squares problems
• Fast computation of the Smith form of a sparse integer matrix
• scientific article; zbMATH DE number 1256647
• On the complexity of inverting integer and polynomial matrices

Cited in

(12)

• Subquadratic-time algorithms for normal bases
• Minimal representations and algebraic relations for single nested products
• Black box methods for least squares problems
• Selecting algorithms for black box matrices, checking for matrix properties that can simplify computations
• When e-th Roots Become Easier Than Factoring
• Complex matrix inversion via real matrix inversions
• Computing the characteristic polynomial of generic Toeplitz-like and Hankel-like matrices
• Solving sparse linear systems faster than matrix multiplication
• Faster modular composition
• Optimal fine-grained hardness of approximation of linear equations
• Solving structured linear systems with large displacement rank
• Algorithms for solving linear systems over cyclotomic fields

Describes a project that uses

Uses Software

• LinBox

This page was built for publication: Faster inversion and other black box matrix computations using efficient block projections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5301663)