In 1965 Klyuev and Kokovkin-Shcherbak proved that n^3/3 + O(n^2) multiplications are necessary to solve an n x n system of linear equations. In 1969 Strassen proved O(n^(log_2 7)) multiplications are sufficient. They could both be right because they considered different models of permitted algorithms. Here we propose yet another algorithmic model, closer in spirit to Klyuev and Kokovkin-Shcherbak, but sufficiently more general to be able to provide lower bounds on the number of arithmetic operations required to perform dense, sparse or "structured" one-sided matrix factorizations: The simplest (and overly restrictive) version of our assumption is that each scalar result is computed using only the data on which it depends mathematically. We compare these lower bounds with a variety of algorithms and matrix sparsity patterns and algebraic structures (such as Vandermonde). Depending on the sparsity patterns and structures, conventional algorithms may or may not attain the lower bounds. In some cases when they do not, we present new algorithms that do, for example for the QR decomposition of a sparse matrix.
An arithmetic complexity lower bound for computing rational functions, with applications to structured and sparse linear algebra
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).