The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented λ algorithms

  • Pan, V.Y.
Publication date
September 1985
Publisher
Published by Elsevier Ltd.
ISSN
0898-1221
Citation count (estimate)
3

Abstract

AbstractThe numbers of bit operations (bt) required for matrix multiplication (MM), matrix inversion (MI), the evaluation of the determinant of a matrix (Det), and the solution of a system of linear equations (SLE) are estimated from above and below. (For SLE the estimates are nearly sharp.) The bit-complexity classes turn out to be different from the arithmetical complexity classes for those problems, for instance, bt(MM) = o(bt(Det)) while MM and Det require the same number of arithmetical operations within a constant factor. The bit complexity gives a more refined measure of stability of algorithms than their condition. In particular the study shows that the large condition of the so called APA algorithms of small degrees for MM causes o...

Extracted data

Loading...

Related items

The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic
  • Pan, V.
December 1982

AbstractThe approximate evaluation with a given precision of matrix and polynomial products is perfo...

Matrix Multiplication, Trilinear Decompositions, APA Algorithms, and Summation
  • Pan, Victor
January 2015

Matrix multiplication (hereafter we use the acronym MM) is among the most fundamental operations of ...

The bit-operation complexity of matrix multiplication and of all pair shortest path problem
  • Pan, V.Ya.
December 1981

AbstractAn N × N matrix product can be evaluated with precision E > 0 in O(Ns+ϵ log (M/E) log log (M...

We use cookies to provide a better user experience.