Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 43
Текст из файла (страница 43)
раздал 4.6.3), две операции вычитания и одно деление, в то время как технический прием во избежание деления, кажется, требует приблизительно втрое больше операций (см. упр. 43). Специальные полнномы от нескольких переменных. Опредсзитель матрицы размера и х и можно рассматривать как полипом от пг переменных х;гэ 1 < 1,/ < и. Если хг2 ф О, то ХИ ХИ ° ° Х1» 221 Х22 ° ° Х2» хи хзг ° ° хз хм — (хг1/хи)хп .-. Х㻠— (хгг/хи)хы хзг — (хзг/хи)хгз ... хз» вЂ” (хзг/хи)хг» = Хил»1 Х»2 — (Х 1/ХИ)Х!2 ..
Х»» (Х»1/ХИ)Х1» (31) Х»1 Х»2 ... Х»» Поэтому определитель матрицы размера и хи можно найти, вычислив определитель матрицы размера (и — 1) х (и — 1) и выполнив дополнительно (и — 1)2+1 умножений, (и — 1)2 сложений и и — 1 делений. Поскольку определитель размера 2 х 2 можно вычислить с помощью двух операций умножения и одной операции сложения, определитель почти всех матриц (т. е, матриц, для которых нет необходимости в делении на нуль) можно вычислить, выполнив максимум (2пз — Зпг + 7п — 6)/6 операций умножения, (2пз — 3яг + и)/6 операций сложения и (пг — и — 2)/2 делений. и + 2 сложений достаточно для всех четных и > 10.
В работе Пана )оТОС 10 (1978), 162-172) также установлено необходимое точное минимальное количество умножений и сложений, когда вычисления производятся полностью с комплексными числами, а не с действительными для всех степеней п, В упр. 40 обсуждается интересная ситуация, возникающая при нечетных значениях и > 9. Ясно, что результаты, полученные для цепочек полиномов с одной переменной, можно без труда применить к полиномам с многими переменными.
Например, если нужно найти оптимальную схему вычисления полинома беэ адаптации коэф- фициентов, можно рассматривать полипом и(х) как поливом от и + 2 переменных хг и„,..., иг, ис; в упр. 38 показано, что в этом случае необходимо и умножений и и сложений. В самом деле, А, Бородин (Т)2ЕОгу О/МаФтеэ апс( Сотрисас!опэ, ееИ1ег( Ьу 2. КоЬат1) и А.
Паз (А. Рах) (Хеге Ъог)с: Асадешгс Ргеээ, 1971, 45-58] доказали, что правило Горнера (2) является, по существу, толью методом вычисления и(х) за 2п операций без предварительных условий. С незначительными изменениями приведенные выше методы могут быть так же хорошо обобщены для цепочек, включающих деление, т. е. для рациональных функций, как и для полиномов. Любопытно, что цепные дроби, аналогичные пра- вилу Горнера, оказались оптимальными с точки зрения вычислительных операций, если скорости выполнения операций умножения и деления одинаковы, даже при дополнительных условиях (см.
упр. 37), Иногда деление полезно во время вычисления полиномов, даже если полиномы определены только в терминах умножения н сложения (соответствующие примеры приводятся в алгоритмах Шо-Трауба для производных полинома), Другим приме- ром является Определитель даже легче вычислить, когда появляется нуль.
Например, если х2! = О, но хг! ф О, получим 312 . ° 31» 2! 322 .. 32» 43! 21 332 . ° 33» 312 31» ззг — (зз1 /зм )хзг . зы — (331/зг ! ) 32» = *и 431 з»2 — (3«!/32!)322, 3«« — (3«!/321)зз« (32) 11 З»2» 3»» Перззанентаозз матрицы называется полипом, который очень похож на определитель, но все его коэффициенты при произведениях членов матрицы равны +1.
Таким образом, Х1« РЕГ:,: = ~~ Х1,,Х2,...Х„г„, х«! ° ° х»« (ЗЗ) где сумма берется по всем перестановкам у1 уг... у„от (1,2,..., и). Казалось бы, эту функцию даже легче вычислить, чем ее более сложную с виду сестру, но не существует метода вычисления перманента матрицы, такого же эффективного, как известные методы для определителя.
В упр. 9 и 10 показано, что достаточно существенно меньшего количества операций и) для больших и, но время счета всех известных методов все еще возрастает по экспоненте с ростом размера матрицы. На самом деле Лесли Г. Велиант 1,еэ)!е О. Уа(!апс) показал, что вычислить заданную 0-1-матрицу так же трудно, как подсчитать число допустимых вычислений машины Тьюринга с недетерминированным полиномиальным временем, если игнорировать полиномиальный характер времени вычислений.
Следовательно, проблемы, связанные с полиномиальным временем вычисления перманента„должны включать множество друп!х хорошо известных проблем, сопротивляющихся эффективному решению за полнномнальное время. С другой стороны, Велиант доказал, что пер- Здесь сокращение размера определителя до (и — 1) х (и — 1) приводит к экономии и — 1 умножений и и — 1 сложений, используемых в (31); это компенсация за дополнительную информацию, необходимую для того, чтобы отличать данный случай.
Таким образом, любой определитель можно вычислить, выполнив приблизительно гнз арифл!етических операций (включая деление). это замечательно, поскольку это полипом с и( членами и и переменными в каждом члене. Для вычисления определителя матрицы с целмззн элементами процедуры (31) и (32) кажутся непривлекательными, так как они требуют рациональной арифметики. Однако можно воспользоваться методом вычисления определителя по шоб р для любого простого числа р, поскольку возможно деление по щи р (упр.
4.5.2 — 16). Если это проделать для достаточного количества простых чисел, то точное значение определителя можно найти так, как объясняется в разделе 4.3.2, поскольку неравенство Адамара 4.6.1 — (25) дает верхнюю грань. Коэффициенты ха)мкгперистическозо пеликана г)ес(х! — Х) матрицы Х размера п х и также можно вычислить за 0(пз) шагов; см. 3. Н. %!1)2!пэоп, ТЬе А)яеЬгв)с Е!Зепга)ие РгоЫет (Ох(оггй Оэхеп!)оп Ргеээ, 1965), 353-355, 410-411, В упр.
70 обсуждается интересный свободный от деления метод, не использующий операции деления и включающий О(пз) !нагов. манент целочисленной матрицы размера п х и можно вычислить по модулю 2 за » 0(п~»») шагов для всех (г > 2. (См. ТЬеоге»5са( Совр. Яс). 8 (1979)„189-201.] Другой связанной с матрицами фундаментальной операцией, конечно, является у»»ноженьке матрац: если Х = (х;.) — матрица размера гл х и, 'г' = (уг») — матрица размера и х э н Е = (зм) — матрица размера и» х э, то формула Я = ХУ означает, что г» =Ях;,У5», 1<1<т, 1<)с<к (34) гьа Это равенство можно рассматривать как вычисление одновременно п»э полиномов от гоп+ пэ переменных; каждмй полинам — "скалярное произведение"' двух и-мерньгх векторов.
Непосредственно вычисление включает тпе умножений и п»э(п — 1) сложений, но Ш. Виноград (Я. Ъ'1побгад) в 1967 году обнаружил, что можно заменить около половины умножений сложениями: гч» = ~~' (хьэг + У»5-1,»Изса5-1 + У»5») а5 Ь» + зыуп»(попс)]~ 1<5<и/3 (35) 5» = ~~~ У»5-ц»У»5,»' 155<в/2 В этой схеме используется ]и/2]п»в + (п52](5п + в) умножений и (и + 2)гпэ + ((п/2] — 1)(гав+ т+ э) сложений или вычитаний; общее число операций возрастает незначительно, но число умножений сокращается приблизительно вдвое.
(См. 1ЕЕЕ Т)впз. С-17 (1968), 693-694.] Поразительная конструкция Винограда побудила многих ученых более внимательно взглянуть на проблему умножения матрицы„что привело к широко распространенному предположению о том, что п»5'2 умножений, возможно, необходимо выполнить для умножения матриц размера и х п, потому что довольно похожая нижняя грань, как известно, имеет место для полиномов с одной переменной.
Еще лучшую схему для больших и открыл в 1968 году Уолкер Штрассен (ЪЪ)кег 8»гвзэеп) „он нашел способ вычисления произведения матриц размера 2 х 2 с помощью всего семи операций умножения, без коммутативности умножения, как в (35). Так как матрицы размера 2п х 2п можно разбить на четыре матрицы размера и х и, его идею можно использовать рекурсивно для получения произведения матриц размера 2» х 2» только с 7» умножениями вместо (2»)з = 8». Порядок роста числа сложений равен 7». Первоначально в методе Штрассена умножения матриц размера 2 х 2 (г5шпег. Ма»Ь.
13 (1969), 354-356] использовалось 7 умножений и 18 сложений; Ш. Виноград позже обнаружил следующую более экономную формулу: с а В 0 ш+и+г((В+С-А-О) ш+н+с где и = (с-а)(С-.0), с = (с+а)(С-А), ю = аА+(с+И-а)(А+Π— С). Если соответствующие промежуточные результаты сохранены, то используется 7 умножений и только 15 сложений; индукцией по й легко показать, что можно умножать матрицы размера 2» х 2" с помощью 7» операций умножения и 5(7» — 4») операций сложения.
Общее число операций, необходимых для умножения матриц размера и х и, следовательно, можно сократить от порядка пз до 0(п'ег) = 0(пз юг4). Подобное для 0 < ег < шы ..., 0 < з„< т„. Слово "преобразование" оправдано, так как можно восстановить значения Р (!ы..., 1„) по значениям Двм.... з„), как показано в упр. 13. В особо важном случае, когда все т = 2, получаем У( ) ~~ ~ ( 1)мц+- +в„ы Р(Г 1 ) (38) ойц,...л„<~ сокращение применяется также к вычислению определителей и обратной матрицы; см. Л, В. ВппсЬ апд 3.
Е. НорсгоЕс, МагЬ. Сошр. 28 (1974), 231-236. До 1978 года несмотря на многочисленные попытки никому не удавалось уменьшить показатель степени Штрассена !8 7, пока Виктор Пан не обнаружил, что он может быть уменьшен до !ойш 143640 ш 2.795 (см. упр. 60). Этот новый прорыв привел к дальнейшему интенсивному исследованию проблемы, н совместные усилия Д. Вини (П. В$п!), М. Каповани (М.
Сарваш), Д. Копперсмита (П. Соррегзш!тЬ), Г. Лотти (6. Босс!), Ф. Романи (Г. Вощап!), А. Шенхаге (А. ЯсЬопЬайе), В. Пана и Ш. Винограда привели к драматическому уменьшению аснмптотики времени счета. В упр. 60-67 обсуждаются интересные технические приемы, благодаря которым установлены такие верхние грани; в частности, в упр.
66 приведено достаточно простое доказательство того, что достаточно 0(п™) операций. Известная до 1997 года лучшая верхняя грань, равная 0(паз~в), предложена в работе Копперсмита и Винограда [Х Яушбо!!с Сошр. 9 (1990), 251-280]. По контрасту лучшая находящаяся в обращении нижняя грань равна 2пз — 1 (см. упр. 12). Эти теоретические результаты совершенно поразительны, но с практической точки зрения они редко используются, так как и должно быть очень большим для того, чтобы можно было преодолеть влияние добавочных факторов.
Ричард Брент (В!сЬагб Вгепс) (Бгапюгд Сошрпсег Яс!енсе герог! СБ157 (МахсЬ, 1970), см. также Хпшег. МаГЬ. 16 (1970), 145-156) нашел, что аккуратное выполнение схемы Винограда (35) с соответствующим масштабированием численной устойчивости будет лучше традиционного метода только прн и > 40.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
