×

Some computational problems in linear algebra as hard as matrix multiplication. (English) Zbl 0774.68056

Summary: We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are:
\(\bullet\) \(KER_ n\): Compute a basis of the kernel for a given \(n\times n\)-matrix,
\(\bullet\) \(OGB_ n\): Find an invertible matrix that transforms a given symmetric \(n\times n\)-matrix (quadratic form) into diagonal form,
\(\bullet\) \(SPR_ n\): Find a sparse representation of a given \(n\times n\)-matrix.
To such a sequence of problems we assign an exponent, similarly as for matrix multiplication. For the complexity of the above problems we prove relative lower bounds of the form \(aM_ n-b\) and absolute lower bounds \(dn^ 2\) where \(M_ n\) denotes the complexity of matrix multiplication and \(a\), \(b\), \(d\) are suitably chosen constants. We show that the exponents of the problem sequences \(KER\), \(OGB\), \(SPR\) are the same as the exponent \(\omega\) of matrix multiplication.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The design and analysis of computer algorithms, Reading MA: Addison-Wesley, 1974. · Zbl 0326.68005
[2] A. Alder andV. Strassen,On the algorithmic complexity of associative algebras, Theor. Computer Science15 (1981), 201-211. · Zbl 0464.68045 · doi:10.1016/0304-3975(81)90070-0
[3] W. Baur andV. Strassen,The complexity of partial derivatives. Theor. Computer Science22 (1982), 317-330. · Zbl 0498.68028 · doi:10.1016/0304-3975(83)90110-X
[4] L. Blum, M. Shub, andS. Smale,On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc.21 (1989), 1-46. · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[5] J. Bunch andJ. Hopcroft,Triangular factorization, and inversion by fast matrix multiplication, Math. Comp.28 (1974), 231-236. · Zbl 0276.15006 · doi:10.1090/S0025-5718-1974-0331751-8
[6] D. Coppersmith andS. Winograd,Matrix multiplication via arithmetic progressions, J. Symb. Comp.9 (1990), 251-280. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[7] R. Hartshorne,Algebraic Geometry, Graduate Texts in Mathematics Vol. 52, Springer Verlag, 1977. · Zbl 0367.14001
[8] K. Kalorkoti,The trace invariant and matrix inversion. Theor. Computer Science59 (1988), 277-286. · Zbl 0648.68058 · doi:10.1016/0304-3975(88)90145-4
[9] W. Keller-Gehrig,Fast algorithms for the characteristic polynomial, Theor. Computer Science36 (1985), 309-317. · Zbl 0565.68041 · doi:10.1016/0304-3975(85)90049-0
[10] H. Kraft,Geometric methods in representation theory, in: Representations of Algebras, Workshop Proc., Puebla, Mexico 1980, LNM944, Berlin-Heidelberg-New York 1982. · Zbl 0512.93034
[11] J. C. Lafon and S. Winograd,A lower bound for the multiplicative complexity of the product of two matrices, (unpublished) manuscript, 1978.
[12] T. Lickteig,On semialgebraic decision complexity, Tech. Rep. TR-90-052 Int. Comp. Science Inst., Berkeley, and Univ. Tübingen, Habilitationsschrift, to appear.
[13] A. Schönhage,Unitäre Transformationen grosser Matrizen, Num. Math.20 (1973), 409-417. · Zbl 0252.65031 · doi:10.1007/BF01402563
[14] V. Strassen,Gaussian elimination is not optimal, Numer. Mathematik13 (1969), 354-356. · Zbl 0185.40101 · doi:10.1007/BF02165411
[15] V. Strassen,Berechnung und Programm I, Acta Informatica1 (1973), 320-335. · Zbl 0252.68018 · doi:10.1007/BF00289512
[16] V. Strassen,Berechnung und Programm II, Acta Informatica2 (1973), 64-79. · Zbl 0258.68022 · doi:10.1007/BF00571464
[17] V. Strassen,Vermeidung von Divisionen, Crelles Journal für die reine und angewandte Mathematik264 (1973), 184-202. · Zbl 0294.65021
[18] V. Strassen,The complexity of continued fraction, SIAM J. Comp.12/1 (1983), 1-27. · Zbl 0543.68026 · doi:10.1137/0212001
[19] V. Strassen,Relative bilinear complexity and matrix multiplication, J. für die reine und angewandte Mathematik375/376 (1987), 406-443. · Zbl 0621.68026 · doi:10.1515/crll.1987.375-376.406
[20] I. Wegener,The complexity of Boolean functions, Wiley-Teubner, 1987. · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.