AOP_Tom2 (1021737), страница 217
Текст из файла (страница 217)
[Н. Наев!ег, Ргас. !21Л Ярг!пб СовЕ Сошрисег СгарЛ!св (Вгабв1ата; Сашешив 1!в!гете!!у, 1996), 55 — 66.] 8. См. (43). 9. (СошЬ!лагат!а! ЛХасЛеглас!св (Вн!Еа1а: МасЬ, Аванс. оЕ Ашег!са, 1963), 26-28.] Эту формулу можно рассматривать как применение принципа включения и исключения (раздел 1.3.3), поскольку сумма членов для и — е~ — — е = Л равна сумме всех х„,хзп...х„„, для которых Л значений у, не появятся. Прямое доказательство можно получить, если заметить, что коэффициент при хп, ... х в„равен если уь различны, это выражение равно единице, однако, если уы ..., у ф Л, равно нулю, поскольку члены с вь — — 0 погашают члены с еь = 1.
Двя эффективного вычисления суммы можно начать с <~ = 1, ез = .. = е = О, а затем пройти все комбинации еь так, чтобы заменить только одно е при переходе от одного члена к другому одним ближайшим членом (см. "серый код" в главе 7). Вычисление первого члена сводится к и — 1 умножению; из последующих 2" — 2 членов каждый требует и сложений, и — 1 умножений и еще одно сложение. Общая сумма операций такова: (2" — 1)(п — 1) умножений и (2" — 2)(п+ 1) сложений.
Необходимо только и+ 1 ячеек для временного хранения промежуточных результатов, одна — для основной частичной суммы и одна— для каждого множителя текущего произведения. 10- ~,<ь<„(Ь + 1)( ",) = п(2" ' — 1) умножений и 2,<„<„Ь( "„,) = п2" ' — 2" + 1 сложений. Это приблизительно половина арифметических операций, необходимых в методе из упр. 9, хата этот метод требует более сложной программы проверки последовательности. Приблизительно ( „"э )+( „",,) ячеек памяти должно быть использовано для временного хранения результатов, и это число растет экспоненциально (порядка 2"/ьГй). Метод в данном упражнении эквивалентен необычному матричному разложению перманента функции, приведенному в работе Юрката и Райзера (зпгЬаг апг) Нуэег, Х А!8ебга 5 (1967), 342-357).
В некотором смысле его также можно рассматривать как применение (39) и (40). 11. Если матрица достаточно плотная, то эффективные методы вычисления приближенного значения известны; см. А. 8!пс!шг, А!бог!гйшэ Гог Еапдош Сепега!!оп апд Свинг!пб (Воз!оп: В!гЬЬапэег, 1993). Но поставленная задача требует вычисления точных значений. Возможно, существует метод вычисления перманента с 0(с") операциями для некоторого с ( 2, 12, Здесь кратко изложены результаты развития этой замечательной научно-исследовательской проблемы: Дж.
Гопкрофт (Х Норсгой) и Л. Р. Кер (Ь. Н. Кегг) между прочим доказали, что необходимо семь умножений для умножения матриц размера 2 х 2 по модулю 2 [ЯАМ Х Арр!. МагЛ. 20 (197Ц, 30-36[ Р. Л. Проберт (Н. Ь. РгоЬегс) показал, что все схемы с семью умножениями, в которых каждое умножение — это умножение линейной комбинации элементов одной матрицы на линейную комбинацию элементов другой матрицы, должно иметь по крайней мере 15 сложений [5!СОМР 5 (1976), 187-203). Ранг тензора умножений матриц размера 2 х 2 бсшьше 7 для любого поля [В.
Я. Пан, Х А!8огВИшз 2 (1981), 301-310), если ранг тензора Т(2, 3, 2) произведения матриц размера 2 х 3 и 3 х 2 равен 11 [В. Б. Алексеев, Х А!8огййшв 6 (1985), 71-85]. Для умножения матриц размера и'х и лучшая верхняя грань известна при и = 3. Ее нашел Д. Д, Ладерман (Х П.
1 абегшап) [Вп!1, Агнес. Маей. Еос. 82 (1976), 126-128), который показал, что достаточно 23 некоммутативных умножений. Его конструкцию обобщил Андрей Сикора. Он предложил метод, требующий и — (и-1) некоммутативных умножений и и -и +11(п — 1) э г з г сложений; этот результат также сводится к (36), когда и = 2 [Ьесэиге Мосек !и Сошр. Яс!. 53 (1977), 504-512).
Для и = 5 рекорд в настоящее время составляет 100 иекоммутативных умножений [О. М. Макаров, СССР, Вычисл. мат. и матем. физика 27, 1 (1987), 205 — 207) Лучшую нижнюю грань, насколько известно, предложили Ж.-К. Лафон (Х-С. Ьа(оп) и Ш. Виноград (8. %1пойгао), которые показали, что необходимо 2п — 1 нескалярных умножений и тп+ па+ т — и — 1 для размерности т х и х в ["А!опег Ьоопб 1ог 1Ье шо1йр1!сабяе согпр1ехВу о!1Ье ргобпсс о! !ко шасг!<Ы', Сев!ге бе Св1сп!, Пшю Ьоп!в Раэсепг (БггавЬоогб, 1979)). Если все вычисления производятся без делении, то для числа операций номного лучшие нижние грани получены Н.
Х. Бшути (К. Н ВэЬоосу) [3!СО5!Р 18 (1989), 759 765). Ои показал, что для умножения по модулю 2 матрицы размера гп хи на матрицу размера и х э требуется по крайней мере 2 'ь ',[та(2~) + -'(и+ (и шог) !))(и — (и шоб!) — !) + и шод 1 умножений, когда и > в > у > 1. Полагая т = и = в и / )8 и, получим, что эта числа равно 2.5пв — -'и 18 и + О(п). Лучшая верхняя грань, известная дэя больших и, обсуждалась в разделе после формулы (36). 13.
Суммируя геометрические ряды, найдем, что Р(1п..., 1„) равно Ев<м <м,,,в<ы < ехр(-2ль(в1Н/т1 + + в„в~/™~)/(вм,,., в„))/пг1... т„. Обратное преобразование от тп1... т» можно найти, выполнив обычное преобразование н заменив !з значениями тз — бм когда !з Ф 0 (см. упр, 4.3.3-9). [Если рассматривать Р(1м...,1„) как коэффициент к" ,... х'„" в полинаме от нескольких переменных, то дискретное преобразование Фурье приравнивается к вычиглению этого полинома в корнях из единицы и обратное преобразование равнозначно нахождению интерполяционного полинома.) 14.
Пусть ш| — — . — — т„ж 2, Р(!ц1з,...,1„) = Р(2" '1„+ + 2вв + 11) и /(вывв,...,в„) = /(2" 'вв + 2" ~вв + . + в„). Заметим, что между вь и в, существует взаимно обратное соответствие. Пусть также дв(вв,..., в„, вв) — это ы в степени 2в '!в(в„+ 2в„1 + .. + 2" ввв). На каждой итерации мы, по существу, .берем 2" ' пар комплексных чисед (а, !3) и заменяем их числами (а+ 6Ц, о — 66), где à — подходящая степень ы. Следовательно, ~ = совд+ вьбпб для некоторого 6.
Если предпочесть упрощении, когда Г = х1 или +л, вся работа сведется к ((и — 3) 2" ' + 2) комплексным умножениям н и 2" комплексным сложениям. Техника упр. 41 может быть использована для уменьшения числа умножений и сложений действительных чисел с помощью операций для коьвплексных чисел. Количество умножений комплексных чисел можно уменьшить приблизительно на 25% без изменения числа сложений, объединяя шаги й и !с + 1 для !в = 1, 3, .... Это означает, что 2" з четверок (а,б,у, б) запенятся выражением (а+ И+ 6'7+ 6'б, о ь !66 — 6'7 — !6 б, о — 66+ 6'7 — 6'б, о — !6/! — 6'У+ !6'б). Общее число умножений комплексных чисел, когда п — четное, в результате уменьшается да (3п — 2)2" в — 5(2" '/3).
В этих вычислениях предполагается, что заданные числа Р(!) — комплексные. Если Р(!) — действительные числа, то /(з) — комплексно-сопряженные к /(2" — в). Таким образом, можно избежать операций, вычисляя только 2" незааисииых действительных чисел /(О), 22/(1), ..., К/(2" ' — 1), /(2" '), В/(1), ..., В/(2" ' — 1). Все вычисления в этом случае могут быть сведены к операциям с 2" действительными числами, если учитываетск тот факт, что /в (в„аз м..., в, 1м, .., 1„в) будут комплексно-сопряженными к /в(в~-в+1 в~ вм..., 1„э), когда (в1... в„)в + (в,... в'„)в — = 0 по модулю 2". Около половины умножений и сложений так же необходимы, как и для комплексных чисел. (Алгоритм быстрого преобразования Фурье открыт К Ф Гауссом в 1805 году и независимо открывался в дальнейшем. Наиболее интересно это сделали Дж. В.
Кули (б. Ъ'. Соо!еу) и Дж. У, Тычки (б, Ч~. Ти1сеу), МааЫ Сошр. 19 (1965), 297-301. Его интересная история прослежена Дж. В. Кули, П. А. У. Левисом и П. Д. Уэлчем (б. Ут'. Соо!еу, Р. А. 1У. 1.ечпв апб Р. Р. 1Уе!<Ь, Ргос. 1ЕЕЕ 55 (1967), 1675-1677); М. Т.
НеЫешап, В. Н, боЬпвоп, апб С. 3. Ваттов, 1ЕЕЕ АМБР Макак!пе 1, 4 (ОссоЬег, 1984), 14-21. Детали, связанные с его применением, обсуждались сотнями авторов; это обсуждение очень кратко изложил Чарлз Ван Лоан (СЬш!сэ Уап 1оап, Сотри Гав/ола! Ргэтеког)<в /ог вЬе Раз! Роиг!ег Тгапв/огш (РЬ!!абе!рЫа: 8!АМ, 1992)). Обзор быстрого преобразования Фурье на конечных группах приводитсн в работе М. С!ааэеп апб Е, Вапш, Еыг РопПег Тгвлв/оппв (МаппЬепп: В!Ы!ойгарЫвсЬев 1пвгВог 1Ч!ввепвсЬа(!втег!аб, 1993).) 15.
(а) Указание вытекает из интегрирования и индукции. Пусть /00(У) берется по всем значениям, лежащим между А и В включительно, когда д изменяется от ппп(хо,, хз) до шах(хо,...,х„), Заменяя /ай каждой из этих граней в вышеприведеннои интеграле, получим А/и! < /(хо,...,х„) < В/п1. (Ь) Достаточно доказать это для 1 = п. Пусть / — интерполяционный полинам Ньютона, тогда /00 равна постоянной и!а„. (См. Тйе Магйешагзсв) Рарегэ о/ Баас №зесоп, еЖей Ьу П. Т. %'Ьзсеззйе, 4 (1971), 36-51, 70 — 73.) 16. Выполнить умножения и сложения (43), как операции над полщгомами. (Частный случай, когда хо = хг = .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
