Space-Time Trade-Offs for Banded Matrix Problems

Publisher Website
Google Scholar
Abstract
Trade-offs between space and time provide ~mportant information on the simultaneous use of these resources. They have been studied most successfully using the Grigoryev method, which leads to lower bounds on the space-time product for certain models of computation. In this paper, we generalize the model to which the Gngoryev method applies and derive space-time lower bounds for banded matnx multiphcatlon and inversion, and for the solution of a set of banded equations. We also investigate full matrix inversion and several other problems. The new computational model consists of algorithms on fimte-state machine with the proviso that input and output are done at times that are data independent. Space is measured by the logarithm of the number of states in the machine, and tame is measured by the number of cycles in which input and/or output is done. We show that standard algorithms for the multiplication ofp x p matrices of bandwith b, and for the inversion of such matrices when b = f~(p) are optimal to within multlphcative factors. Good algorithms are also presented for the soluUon of a set of banded equations and for banded matrix inversion. Categories and Subject Descriptors: F.2.3 (Analysis of Algorithms Problem Complexity(: Trade-Offs among Complexity Measures; G. 1 3 (Numerical Analysisl" Numerical Linear Algabra-hnear systems

This publication has 4 references indexed in Scilit: