×

zbMATH — the first resource for mathematics

Fast rectangular matrix multiplication and applications. (English) Zbl 0919.65030
D. Coppersmith and S. Winograd [J. Symb. Comput. 9, No. 3, 251-280 (1990; Zbl 0702.65046)] published an algorithm for \(n \times n\) matrix multiplication requiring \(O(n^\omega)\) arithmetic operations, with \(\omega< 2.376\). The present authors extend the method to multiplication of an \(n\times n\) matrix by an \(n\times n^2\) matrix requires \(O(n^\omega)\) arithmetic operations, with \(\omega< 3.334\), less than the previous record by 0.041. After this, the method is extended to fast multiplication of matrix pairs of arbitrary dimension and in many cases improvements are made. Known exponents for fast parallel determination of the solution of linear systems and the related computation of determinant and inverse, are reduced slightly from 2.851 to 2.837.
Other applications discussed are sequential algorithms for univariate polynomial factorization over a finite field and a slight improvement to the computational complexity of the linear programming problem with \(m\) constraints and \(n\) variables.

MSC:
65F30 Other matrix algorithms (MSC2010)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
65Y20 Complexity and performance of numerical algorithms
90C05 Linear programming
65H05 Numerical computation of solutions to single equations
65K05 Numerical mathematical programming methods
65Y05 Parallel numerical computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berlekamp, E.R., Factoring polynomials over large finite fields, Math. comput., 24, 713-735, (1970) · Zbl 0247.12014
[2] Bini, D.; Capovani, M.; Lotti, G.; Romani, F., On2.7799, Inform. process. lett., 8, 234-235, (1979)
[3] Bürgisser, P.; Clausen, M.; Shokrollahi, M.A., Algebraic computational complexity, (1997), Springer Berlin · Zbl 1087.68568
[4] Brockett, R.W.; Dobkin, D., On the number of multiplications required for matrix multiplications, SIAM J. complexity, 5, 624-628, (1976) · Zbl 0345.65011
[5] Behrend, F.A., On sets of integers which contain no three terms in arithmetical progression, Proc. nat. acad. sci. USA, 32, 331-332, (1946) · Zbl 0060.10302
[6] Brent, R.P.; Kung, H.T., Fast algorithms for manipulating formal power series, J. assoc. comput. Mach., 25, 581-595, (1978) · Zbl 0388.68052
[7] Borodin, A.; Munro, I., The computational complexity of algebraic and numeric problems, (1975), American Elsevier New York · Zbl 0404.68049
[8] Beling, P.A.; Megiddo, N., Using fast matrix multiplication to find basic solutions, Theoret. comput. sci., (1998) · Zbl 0913.68079
[9] Bini, D.; Pan, V.Y., Polynomial and matrix computations, vol. 1: fundamental algorithms, (1994), Birkhäuser Boston
[10] Coppersmith, D., Rapid multiplication of rectangular matrices, SIAM J. comput., 11, 467-471, (1982) · Zbl 0486.68031
[11] Coppersmith, D., Rectangular matrix multiplication revisited, J. complexity, 13, 42-49, (1997) · Zbl 0872.68052
[12] Coppersmith, D.; Winograd, S., On the asymptotic complexity of matrix multiplication, SIAM J. comput., 11, 472-492, (1982) · Zbl 0486.68030
[13] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. symbolic comput., 9, 251-280, (1990) · Zbl 0702.65046
[14] Cantor, D.G.; Zassenhaus, H., A new algorithm for factoring polynomials over finite fields, Math. comput., 36, 587-592, (1981) · Zbl 0493.12024
[15] Eberly, W., Parallel matrix inversion over abstract fields: two approaches, Proceedings second international symposium on parallel symbolic computation (PASCO’97), (1997), ACM Press New York, p. 38-45 · Zbl 0917.65024
[16] Eppstein, D.; Galil, Z., Parallel algorithmic techniques for combinatorial computation, Annual rev. comput. sci., 3, 233-283, (1988)
[17] Golub, G.H.; Van Loan, C.F., Matrix computations, (1996), Johns Hopkins Univ. Press Baltimore · Zbl 0865.65009
[18] Galil, Z.; Pan, V.Y., Parallel evaluation of the determinant and of the inverse of a matrix, Infor. proc. lett., 30, 41-45, (1989) · Zbl 0664.68040
[19] von zur Gathen, J.; Shoup, V., Computing Frobenius maps and factoring polynomials, Comput. complexity, 2, 187-224, (1992) · Zbl 0778.11076
[20] Kaltofen, E.; Pan, V.Y., Processor efficient parallel solution of linear systems over an abstract field, Proceedings, 3rd annual ACM symposium on parallel algorithms and architectures, (1991), ACM Press New York, p. 180-191
[21] Kaltofen, E.; Pan, V.Y., Processor-efficient parallel solution of linear systems. II. the positive characteristic and singular case, Proceedings of 33rd annual IEEE symposium on foundations of computer science, (1992), IEEE Computer Society Press Los Alamitos, p. 714-723 · Zbl 0977.68879
[22] Kaltofen, E.; Pan, V.Y., Parallel solution of Toeplitz and Toeplitz-like linear systems over fields of small positive characteristic, Proceedings of first international symposium on parallel symbolic computation (PASCO’94), Linz, Austria (sept. 1994), Lecture notes series in computing, 5, (1994), World Scientific Singapore, p. 225-233
[23] Karp, R.; Ramachandran, V., A survey of parallel algorithms for shared memory machines, Handbook for theoretical computer science, (1990), North Holland Amsterdam, p. 869-941 · Zbl 0900.68267
[24] Kaltofen, E.; Shoup, V., Subquadratic-time factoring of polynomials over finite fields, Proceedings, 27th annual ACM symposium on theory comput., (1995), ACM Press New York, p. 398-406 · Zbl 0921.11068
[25] Pan, V.Y., On schemes for the computation of products and inverses of matrices, Uspekhi mat. nauk., 27, 249-250, (1972)
[26] Pan, V.Y., How to multiply matrices faster, Lecture notes in computer science, 179, (1984), Springer Berlin
[27] Pan, V.Y., How can we speed-up matrix multiplication?, SIAM rev., 26, 393-415, (1984) · Zbl 0563.65028
[28] Pan, V.Y., Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Theor. comput. sci., 162, 173-233, (1996) · Zbl 0874.12010
[29] Schönhage, A., Partial and total matrix multiplication, SIAM J. comput., 10, 434-456, (1981) · Zbl 0462.68018
[30] Salem, R.; Spencer, D.C., On sets of integers which contain no three terms in arithmetical progression, Proc. nat. acad. sci. USA, 28, 561-563, (1942) · Zbl 0060.10301
[31] Strassen, V., Gaussian elimination is not optimal, Numerische math., 13, 354-356, (1969) · Zbl 0185.40101
[32] Strassen, V., The asymptotic spectrum of tensors and the exponent of matrix multiplication, Proceedings, 27th annual IEEE symposium on foundations of computer science, (1986), IEEE Computer Society Press, p. 49-54
[33] Strassen, V., Relative bilinear complexity and matrix multiplication, J. reine angew. math., 375/376, 406-443, (1987) · Zbl 0621.68026
[34] Strassen, V., The asymptotic spectrum of tensor, J. reine angew. math., 384, 102-152, (1988) · Zbl 0631.68033
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.