GAUSSIAN ELIMINATION IS NOT OPTIMAL
GAUSSIAN ELIMINATION IS NOT OPTIMAL
复制标题
DOI：
10.1007/bf02165411
复制
发表时间：
1969-01-01
影响因子：
2.1
通讯作者：
STRASSEN, V
中科院分区：
文献类型：
--
作者：
STRASSEN, V
12月12日收到，吨968吨。下面我们将给出一种算法，该算法根据 A 和 B 的系数计算两个 n 阶方阵 A 和 B 的乘积的系数，其运算次数少于 4.7-nlg7 次（本文中所有对数均以 2 为底，因此为 7~ 2.8；通常的方法大约需要 2n 3 次算术运算）。该算法引入了用于求逆 n 阶矩阵、求解 n 个未知数中的 n 个线性方程组、计算 n 阶行列式等的算法，所有这些都需要少于 const nlg 7 次算术运算。这一事实应该与 KLYUYEV 和 KOKOVKINSHCHERBAK [1] 的结果进行比较，即如果将自己限制为对行和列作为一个整体进行运算，则求解线性方程组的高斯消元法是最佳的。我们还注意到，WlNOGRAD [21 修改了矩阵乘法和求逆以及求解线性方程组的常用算法，将大约一半的乘法换成了加法和减法。很高兴感谢 D. BRILLINGER 就当前主题和 ST 进行的启发性讨论。 COOK 和 B. PARLETT 鼓励我写这篇论文。 2. 我们定义算法 e~,~ 乘以 m2 阶矩阵，通过 k:~, 0 是常用算法，对于矩阵乘法（需要 ma 乘法和 m 2 (m-t) 加法），e~, k 已经已知，定义~,~+ t 如下：
Received December 12, t 968 t. Below we will give an algorithm which computes the coefficients of the product of two square matrices A and B of order n from the coefficients of A and B with tess than 4.7-nlg7 arithmetical operations (all logarithms in this paper are for base 2, thus tog 7~ 2.8; the usual method requires approximately 2n 3 arithmetical operations). The algorithm induces algorithms for inverting a matrix of order n, solving a system of n linear equations in n unknowns, computing a determinant of order n etc. all requiring less than const nlg 7 arithmetical operations.This fact should be compared with the result of KLYUYEV and KOKOVKINSHCHERBAK [1] that Gaussian elimination for solving a system of linearequations is optimal if one restricts oneself to operations upon rows and columns as a whole. We also note that WlNOGRAD [21 modifies the usual algorithms for matrix multiplication and inversion and for solving systems of linear equations, trading roughly half of the multiplications for additions and subtractions. It is a pleasure to thank D. BRILLINGER for inspiring discussions about the present subject and ST. COOK and B. PARLETT for encouraging me to write this paper. 2. We define algorithms e~,~ which multiply matrices of order m2, by induction on k:~, 0 is the usual algorithm, for matrix multiplication (requiring ma multiplications and m 2 (m-t) additions), e~, k already being known, define~,~+ t as follows: