TL;DR
This paper demonstrates how Strassen's fast matrix multiplication algorithm can be used to achieve faster triangular factorization and matrix inversion. By cleverly applying Strassen's method recursively, the authors show that these fundamental linear algebra operations can be performed with a computational complexity significantly lower than traditional methods, approaching the theoretical limits set by fast matrix multiplication.
What Problem Does This Paper Address?
For decades, the standard algorithms for matrix multiplication, triangular factorization (like LU decomposition), and matrix inversion have relied on methods with cubic time complexity, typically denoted as O(n³). While efficient for smaller matrices, these algorithms become computationally prohibitive for very large matrices. Strassen's groundbreaking work in 1969 introduced a matrix multiplication algorithm with a complexity of O(n^log₂7) ≈ O(n².81), which is asymptotically faster than the O(n³) of the standard method. However, the question remained: could this speedup be extended to other essential linear algebra operations like factorization and inversion? This paper tackles that challenge, aiming to adapt Strassen's fast multiplication to achieve similar asymptotic speedups for these related problems.
Methods
The core of this paper lies in adapting Strassen's recursive matrix multiplication algorithm to perform triangular factorization and inversion. The authors build upon the idea of block matrix operations. They recursively decompose matrices into smaller sub-blocks and apply Strassen's multiplication to compute the necessary intermediate products.
Key techniques include:
- Block LDU Factorization: The paper starts by considering block LDU factorization, a standard technique where a matrix is decomposed into a lower triangular matrix (L), a diagonal matrix (D), and an upper triangular matrix (U).
- Recursive Application of Strassen's Multiplication: The crucial innovation is to use Strassen's algorithm for the matrix multiplications that arise within the recursive steps of the factorization and inversion process. For example, when computing the inverse of a block matrix, terms like $A_{21}A_{11}^{-1}A_{12}$ appear, where $A_{11}^{-1}$ is computed recursively and then multiplied by $A_{21}$ and $A_{12}$. Strassen's method is employed for these multiplications.
- Pivoting: To handle general nonsingular matrices (not just symmetric positive definite ones), the algorithm incorporates pivoting (row and column interchanges) to ensure that the necessary sub-blocks are invertible during the recursive process.
- Modified Algorithm for Reduced Coefficients: The authors present a modified algorithm that further reduces the leading coefficients of the complexity bounds, particularly by using standard multiplication for submatrices below a certain size (e.g., 8x8). This is a common practice in fast matrix algorithms to balance the overhead of recursion with the gains from faster multiplication.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithm design and complexity analysis, not empirical evaluation on specific datasets.
Key Insights and Ideas
- Equivalence of Computational Complexity: A major takeaway is the demonstration that matrix multiplication, triangular factorization, and inversion are computationally equivalent. This means that if you have a fast algorithm for one, you can derive a fast algorithm for the others with only a modest increase in the exponent of the complexity.
- Strassen's Speedup Extends: The paper proves that Strassen's O(n^log₂7) complexity can indeed be applied to triangular factorization and inversion, not just multiplication. This is a significant theoretical result for linear algebra.
- The Importance of Pivoting: The authors highlight that for general nonsingular matrices, pivoting is essential to make the recursive block factorization work, as it ensures that the diagonal blocks remain invertible throughout the process.
- Trade-off Between Recursion Depth and Base Case: The modified algorithm shows that there's an optimal point for switching from the fast recursive method to standard algorithms for small submatrices, balancing the overhead of recursion with the asymptotic gains.
Key Results
The paper provides theoretical bounds on the number of operations (multiplications, divisions, additions, subtractions) required for triangular factorization and inversion using Strassen's method. For matrices of order $n=2^k$:
- Triangular Factorization: Achieved in $< (3.64)n^{\log_2 7}$ operations.
- Matrix Inversion: Achieved in $< (10.18)n^{\log_2 7}$ operations.
For arbitrary $n$, the bounds are slightly higher but still asymptotically faster than O(n³):
- Triangular Factorization: $< (2.45)n^{\log_2 7}$ operations.
- Matrix Inversion: $< (6.84)n^{\log_2 7}$ operations.
These results represent a significant theoretical improvement over the O(n³) complexity of traditional Gaussian elimination and inversion methods.
Limitations and Future Work
- Numerical Stability: The authors explicitly acknowledge that the presented algorithm may not be numerically stable. The recursive nature and the potential for elements in reduced matrices to grow unbounded are concerns. They suggest that further investigation into modifications that guarantee stability is needed.
- Constant Factors: While the asymptotic complexity is improved, the leading constants in the operation counts are larger than those for standard algorithms. This means that for practical matrix sizes, the standard O(n³) algorithms might still be faster due to lower overhead. The paper mentions that a proposed method by A. Schönhage has a larger constant factor for inversion.
- Generalization to Rings: The paper briefly touches upon the possibility of extending these algorithms to operate over any ring, which is an interesting avenue for future research.
Summary updated