Faster Sparse Matrix Inversion and Rank Computation in Finite Fields
summary
Claims a faster algorithm for inverting sparse n-by-n matrices over finite fields with expected time about O(n^{2.2131}) for O(n) nonzeros, by reducing A^{-1} to Krylov × block-Hankel inverse × Krylov and computing the block-Hankel inverse via displacement operators and compressed rectangular generators. The method uses randomized preconditioning, rectangular generator recovery, and fast rectangular matrix multiplication to expand generators; the final runtime scales with the rectangular-multiplication exponent, so any improvement there lowers this bound.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:22SOLVING LINEAR SYSTEMS
- 1:06MATRIX INVERSION & COMPLEXITY QUESTIONS
- 3:31ALGORITHMS IN FINITE FIELDS
- 5:20FROM FINITE FIELDS TO THE REALS
- 6:27THIS TALK: MATRIX INVERSION
- 7:11NOTATION
- 7:50THE SET-UP
- 9:35OBTAINING A BLOCK HANKEL MATRIX
- 12:44DISPLACEMENT RANK THEOREM
- 13:10THE DUAL OPERATOR
- 14:49SUCCINT REPRESENTATION OF THE INVERSE
- 15:37BABO ALGORITHM
- 16:53OTHER TYPES OF DISPLACEMENT OPERATORS
- 18:52EXPLICIT RECOVERY
- 21:08GENERAL SCHEME
- 21:52RETURNING TO MATRIX INVERSE
- 25:04MAIN TAKE-AWAYS