An arithmetic complexity lower bound for computing rational functions, with applications to structured and sparse linear algebra

James Demmel

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2018-82
May 19, 2018

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-82.pdf

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.


BibTeX citation:

@techreport{Demmel:EECS-2018-82,
    Author = {Demmel, James},
    Title = {An arithmetic complexity lower bound for computing rational functions, with applications to structured and sparse linear algebra},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2018},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-82.html},
    Number = {UCB/EECS-2018-82},
    Abstract = {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.}
}

EndNote citation:

%0 Report
%A Demmel, James
%T An arithmetic complexity lower bound for computing rational functions, with applications to structured and sparse linear algebra
%I EECS Department, University of California, Berkeley
%D 2018
%8 May 19
%@ UCB/EECS-2018-82
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-82.html
%F Demmel:EECS-2018-82