Определитель даже легче вычислить, когда появляется нуль. Например, если Хц = О, но xii ф О, получим

- Х21 det

X32 - (X3l/X2l)X22 ХЗп - {X3l/X2l)X2n \хп2 - {XnllX2\)X22 Xnn - /X21 )X2n/

(32)

Здесь сокращение размера определителя до (п - 1) х (п - 1) приводит к экономии п - 1 умножений и п - 1 сложений, используемых в (31); это компенсация за дополнительную информацию, необходимую для того, чтобы отличать данный случай. Таким образом, любой определитель можно вычислить, выполнив приблизительно арифметических операций (включая деление). Это замечательно, поскольку это полином с п! членами и п переменными в каждом члене.

Для вычисления определителя матрицы с целыми элементами процедуры (31) и (32) кажутся непривлекательными, так как они требуют рациональной арифметики. Однако можно воспользоваться методом вычисления определителя по mod р для любого простого числа р, поскольку возможно деление по mod р (упр. 4.5.2-16). Если это проделать для достаточного количества простых чисел, то точное значение определителя можно найти так, как объясняется в разделе 4.3.2, поскольку неравенство Адамара 4.6.1-(25) дает верхнюю грань.

Коэффициенты характеристического полинома det(a;J - X) матрицы X размера п х п также можно вычислить за 0{п) шагов; см. J. Н. Wilkinson, The Algebraic Eigenvalue Problem (Oxford: Clarendon Press, 1965), 353-355, 410-411. В упр. 70 обсуждается интересный свободный от деления метод, не использующий операции деления и включающий 0{п*) шагов.

Перманентом матрицы называется полином, который очень похож на определитель, но все его коэффициенты при произведениях членов матрицы равны -Hi. Таким образом,

/Хц ... Xin\

(33)

\Xnl . Хпп/

где сумма берется по всем перестановкам ji J2 • • • jn от {1,2,..., n}. Казалось бы, эту функцию даже легче вычислить, чем ее более сложную с виду сестру, но не существует метода вычисления перманента матрицы, такого же эффективного, как известные методы для определителя. В упр. 9 и 10 показано, что достаточно существенно меньшего количества операций п! для больших п, но время счета всех известных методов все еще возрастает по экспоненте с ростом размера матрицы. На самом деле Лесли Г. Велиант Leslie G. Valiant) показал, что вычислить заданную 0-1-матрицу так же трудно, как подсчитать число допустимых вычислений машины Тьюринга с недетерминированным полиномиальным временем, если игнорировать полиномиальный характер времени вычислений. Следовательно, проблемы, связанные с полиномиальным временем вычисления перманента, должны включать множество других хорошо известных проблем, сопротивляющихся эффективному решению за полиномиальное время. С другой стороны, Велиант доказал, что пер-

манент целочисленной матрицы размера пхп можно вычислить по модулю 2* за 0(п**-) шагов для всех к>2. [См. Theoreticai Сотр. Sci. 8 (1979), 189-201.]

Другой связанной с матрицами фундаментальной операцией, конечно, является умножение матриц: если X = (ху) -матрица размера mxn,Y = (yjk) - матрица размера п х s и Z = (zik) - матрица размера m х s, то формула Z = ХУ означает, что

Zik = 2 Xijyjk, l<i<m, l<fc<s. (34)

Это равенство можно рассматривать как вычисление одновременно ms полиномов от тп + ns переменных; каждый полином - "скалярное произведение" двух п-мерных векторов. Непосредственно вычисление включает mns умножений и ms{n - 1) сложений, но Ш. Виноград (S. Winograd) в 1967 году обнаружил, что можно заменить около половины умножений сложениями:

Zik= {Xi,2j+y2j-i,k)ixi,2j-i + y2j,k) - ai - Ьк + Xinynk[noM];

l<J<n/2

а» = Xi,2jXi2j-i; bk=- y2j-i,ky2j,k- (35)

l<J<n/2 l<J<n/2

В этой схеме используется [n/2]ms + [n/2J(m + s) умножений и (n -Н 2)ms + ([n/2j - l)(ms + m + s) сложений или вычитаний; общее число операций возрастает незначительно, но число умножений сокращается приблизительно вдвое. [См. ШЕЕ Ttans. С-17 (1968), 693-694.] Поразительная конструкция Винограда побудила многих ученых более внимательно взглянуть на проблему умножения матрицы, что привело к широко распространенному предположению о том, что п/2 умножений, возможно, необходимо выполнить для умножения матриц размера пхп, потому что довольно похожая нижняя грань, как известно, имеет место для полиномов с одной переменной.

Еще лучшую схему для больших п открыл в 1968 году Уолкер Штрассен (Volker Strassen); он нашел способ вычисления произведения матриц размера 2 х 2 с помощью всего семи операций умножения, без коммутативности умножения, как в (35). Так как матрицы размера 2п х 2п можно разбить на четыре матрицы размера пхп, его идею можно использовать рекурсивно для получения произведения матриц размера 2* х 2* только с 7* умножениями вместо (2*) = 8*. Порядок роста числа сложений равен 7*. Первоначально в методе Штрассена умножения матриц размера 2x2 [JVumer. Math. 13 (1969), 354-356] использовалось 7 умножений и 18 сложений; Ш. Виноград позже обнаружил следующую более экономную формулу:

а Ь\ГА C\f аЛ+ЬВ w+v+ia+b-c-d)D\

с d)\B D)~\w+u+d{B+C-A-D) w+u+v )

гдеи = (c-a)(C-D), v = {c+d){C-A), w = aA+{c+d-a){A+D -C). Если соответствующие промежуточные результаты сохранены, то используется 7 умножений и только 15 сложений; индукцией по к легко показать, что можно умножать матрицы размера 2* х 2* с помощью 7* операций умножения и 5(7* - 4*) операций сложения. Общее число операций, необходимых для умножения матриц размера п х п, следовательно, можно сократить от порядка п до 0(п8) = ©(п-*"*). Подобное

сокращение применяется также к вычислению определителей и обратной матрицы; см. J. R. Bunch and J. Е. Hopcroft, Math. Сотр. 28 (1974), 231-236.

До 1978 года несмотря на многочисленные попытки никому не удавалось уменьшить показатель степени Штрассена lg7, пока Виктор Пан не обнаружил, что он может быть уменьшен до logo 143640 и 2.795 (см. упр. 60). Этот новый прорыв привел к дальнейшему интенсивному исследованию проблемы, и совместные усилия Д. Вини (D. Bini), М. Каповани (М. Capovani), Д. Копперсмита (D. Coppersmith), Г. Лотти (G. Lotti), Ф. Романи (F. Romani), А. Шёнхаге (А. Schonhage), В. Пана и Ш. Винограда привели к драматическому уменьшению асимптотики времени счета. В упр. 60-67 обсуждаются интересные технические приемы, благодаря которым установлены такие верхние грани; в частности, в упр. 66 приведено достаточно простое доказательство того, что достаточно 0(п-) операций. Известная до 1997 года лучшая верхняя грань, равная 0{п), предложена в работе Копперсмита и Винограда [J. SymboUc Сотр. 9 (1990), 251-280]. По контрасту лучшая находящаяся в обращении нижняя грань равна 2п - 1 (см. упр. 12).

Эти теоретические результаты совершенно поразительны, но с практической точки зрения они редко используются, так как п должно быть очень большим для того, чтобы можно было преодолеть влияние добавочных факторов. Ричард Брент (Richard Brent) [Stanford Computer Science report CS157 (March, 1970), см. также JVumer. Math. 16 (1970), 145-156] нашел, что аккуратное выполнение схемы Винограда (35) с соответствующим масштабированием численной устойчивости будет лучше традиционного метода только при п > 40. К тому же будет сэкономлено всего 7% времени счета, когда п - 100. Для комплексной арифметики ситуация отчасти иная; схема (35) становится благоприятной для п > 20, и экономится 18% времени при п = 100. Брент оценил, что схема Штрассена (36) не превосходит (35) до тех пор, пока п и 250. Такие огромные матрицы на практике встречаются нечасто, поэтому применяются другие технические приемы. Кроме того, известные методы порядка п", где о; < 2.7, имеют такую большую константу пропорциональности, что потребуется более 10 умножений, прежде чем они превзойдут (36).

По контрасту следующие методы, которые мы обсудим, очень практичны и находят широкое применение. Дискретное преобразование Фурье / комплексно-значной функции F от п переменных по соответствующей области ту, т„ элементов определяется равенством

/(si,.-.,sn)- е ехр(27гг( + .-. + )) F(tb...,t„) (37)

0<tn<m„

ДЛЯ о < Si < mi, ..., о < s„ < m„. Слово "преобразование" оправдано, так как можно восстановить значения F{ti,..., t„) по значениям /(si,..., s„), как показано в упр. 13. В особо важном случае, когда все mj = 2, получаем

/(si,...,s„)= Y1 i-iy--""F{ti,..-,tn) (38)

0<ti,...,«„<l