PDF

Description

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.

Details

Files

Statistics

from
to
Export
Download Full History