Вычисления оказываются идентичными вычислениям на шагах HI и Н2, но выполняются в другом порядке. (Фактически это воплощение первоначальных идей Ньютона, связанные с использованием схемы (2).)

3. Коэффициент при равен полиному от у, который можно вычислить по правилу Горнера: (... {и„,ох + («„ i,ij/ + «„ i,o))x + • • •)х + ((... (ио,пУ + «o,n-i)y + }у + «о,о).

[Для "однородного" полинома, такого как «„х" + Un-ix"~y Ч----+ щху" + иоу", более

эффективна другая схема: если О < х < у, сначала разделить х на у, вычислить полином от х/у, а затем умножить на у".]

4. Правило (2) включает 4п или Зп вещественных умножений и 4п или 7п вещественных сложений; схема (3) хуже: она требует 4п + 2 или 4п + I умножений, Ап + 2 или 4п + 5 сложений.

5. Одно умножение для вычисления х; [n/2J умножений и [n/2J сложений для вычисления первой строки; fn/2] умножений и fn/2] - 1 сложений для вычисдения второй строки и одно сложение для суммирования обеих строк. Всего п+1 умножений и п сложений.

6. Л. Вычислить и запомнить значения хо, xq, ..., Хо"! J2. Присвоить Dj •«- UjX--"- для О < j < п.

J3. При А; = О, 1, ..., п - 1 присвоить Vj Vj + Vj+i при j = п - 1, ..., к + 1, к. J4. Присвоить Vj VjXq"~ для О < j < п.

Здесь (п + п)/2 сложений, п + [п/2] - 1 умножений и п делений. Еще одно умножение и деление можно сэкономить, если трактовать t;„ и vo как частные случаи [см. SIGACT News 7,3 (Summer, 1975), 32-34].

7. Пусть Xj = xo + jh. Рассмотрим (42) и (44). Присвоить yj u(xj) для О < j < п. Для А; = 1, 2, ..., п (в таком порядке) присвоить yj yj - yj-i при j = п, п - 1, ..., к (в таком порядке). Присвоить 0j yj для всех j.

Тем не менее, как объяснялось в разделе, ошибка округления будет накапливаться, даже если операции (5) выполняются с великолепной точностью. Лучшим способом осуществления инициализации, когда (5) выполняется с арифметикой с фиксированной точкой, является выбор /Зо, , 0п таким образом, что

где ео, ei, еп настолько малы, насколько это возможно. [Н. Hassler, Proc. 12tii Spring Conf. Computer Graphics (Bratislava: Comenius University, 1996), 55-66.]

8. Cm. (43).

9. [Combinatorial JVfatiiematics (Buffalo: Math. Assoc. of America, 1963), 26-28.] Эту формулу можно рассматривать как применение принципа включения и исключения (раздел 1.3.3), поскольку сумма членов для п - ei - • • • - «п = к равна сумме всех xijiX2j2 .. .x„j„, для которых к значений ji не появятся. Прямое доказательство можно получить, если заметить, что коэффициент при xiji .. .Xnj„ равен

если jk различны, это выражение равно единице, однако, если ji, . ., jn ф к, равно нулю, поскольку члены с е*, = О погашают члены се*, =1.

Для эффективного вычисления суммы можно начать с ei = 1, ез = • • • = «п = О, а затем пройти все комбинации tk так, чтобы заменить только одно е при переходе от одного члена к другому одним ближайшим членом (см. "серый код" в главе 7). Вычисление первого члена сводится к п - 1 умножению; из последующих 2" - 2 членов каждый требует п сложений, п-1 умножений и еще одно сложение. Общая сумма операций такова: (2" - 1)(п - 1) умножений и (2" - 2)(п + 1) сложений. Необходимо только п + 1 ячеек для временного хранения промежуточных результатов, одна - для основной частичной суммы и одна- для каждого множителя текущего произведения.

10- Ei<*<„(s + 1)G:J = n(2"- - 1) умножений и Ei<k<nKkli) = «2- - 2" + 1 сложений. Это приблизительно половина арифметических операций, необходимых в методе из упр. 9, хотя этот метод требует более сложной программы проверки последовательности. Приблизительно (-„"2i)"*(rn/2i-i) ячеек памяти должно быть использовано для временного хранения результатов, и это число растет экспоненциально (порядка 2"/0»).

Метод в данном упражнении эквивалентен необычному матричному разложению перманента функции, приведенному в работе Юрката и Райзера (Jurkat and Ryser, J. Algebra 5 (1967), 342-357). В некотором смысле его также можно рассматривать как применение (39) и (40).

11. Если матрица достаточно плотная, то эффективные методы вычисления приближенного значения известны; см. А. Sinclair, Algorithms for Random Generation and Counting (Boston: Birkhauser, 1993). Ho поставленная задача требует вычисления точных значений. Возможно, существует метод вычисления перманента с 0(с") операциями для некоторого с < 2.

12. Здесь кратко изложены результаты развития этой замечательной научно-исследовательской проблемы: Дж. Гопкрофт (J. Hopcroft) и Л. Р. Кер (L. R. Kerr) между прочим доказали, что необходимо семь умножений для умножения матриц размера 2 х 2 по модулю 2 [SIAM J. Appl. Math. 20 (1971), 30-36]. P. Л. Проберт (R. L. Probert) показал, что все схемы с семью умножениями, в которых каждое умножение - это умножение линейной комбинации элементов одной матрицы на линейную комбинацию элементов другой матрицы, должно иметь по крайней мере 15 сложений [SICOMP 5 (1976), 187-203]. Ранг тензора умножений матриц размера 2x2 больше 7 для любого поля [В. Я. Пан, J. A7goritiinjs 2 (1981), 301-310], если ранг тензора Т(2,3,2) произведения матриц размера 2 X 3 и 3 X 2 равен И [В. Б. Алексеев, J. Algorithms 6 (1985), 71-85]. Для умножения матриц размера пхп лучшая верхняя грань известна при п = 3. Ее нашел Д. Д. Ладерман (J. D. Laderman) [Bull. Amer. Math. Soc. 82 (1976), 126-128], который показал, что достаточно 23 некоммутативных умножений. Его конструкцию обобщил Андрей Сикора. Он предложил метод, требующий n-(n-l) некоммутативных умножений и n-n+ll(n-l) сложений; этот результат также сводится к (36), когда п = 2 [Lecture Notes in Сотр. Sci. 53 (1977), 504-512]. Для n = 5 рекорд в настоящее время составляет 100 некоммутативных умножений [О. М. Макаров, СССР, Вычисл. мат. и матем. физика 27,1 (1987), 205-207]. Лучшую нижнюю грань, насколько известно, предложили Ж.-К. Лафон (J.-C. Lafon) и Ш. Виноград (S. Winograd), которые показали, что необходимо 2п - 1 нескалярных умножений и тп + ns + m - п-1 для размерности т у. п у. s ["А lower bound for the multiplicative complexity of the product of two matrices", Centre de Calcul, Univ. Louis Pasteur (Strasbourg, 1979)]. Если все вычисления производятся без деления, то для числа операций немного лучшие нижние грани получены Н. X. Бшути (N. Н. Bshouty) [SICOMP 18 (1989), 759-765]. Он показал, что для умножения по модулю 2 матрицы размера m х п на матрицу размера пх s требуется по крайней мере

Ei=oL"»«/2*J + (п+ (п modj))(n- (nmod j) - j) +nmodj

умножений, когда п > s > j > 1. Полагая m = п = s и j а Ign, получим, что это число равно 2.5п - nlgn + 0{n).

Лучшая верхняя грань, известная для больших п, обсуждалась в разделе после формулы (36).

13. Суммируя геометрические ряды, найдем, что F{ti,. ..,t„) равно

Eo<.,<mi.....о<,„<тп exp(-27ri(siti/mi + • • + s„t„/m„)/(si,... ,5„))/mi ... m„.

Обратное преобразование от mi... тп можно найти, выполнив обычное преобразование и заменив tj значениями mj - tj, когда tj ф О (см. упр. 4.3.3-9).

[Если рассматривать F{t\, ...,tn) как коэффициент ... xJ," в полиноме от нескольких переменных, то дискретное преобразование Фурье приравнивается к вычислению этого полинома в корнях из единицы и обратное преобразование равнозначно нахождению интерполяционного полинома.]

14. Пусть mi = •• = m„ = 2, F{ti,t2,... ,tn) = F{2"-4n + + 2t2 + ti) и f{si,S2,. ,Sn) = /(2"-Si -I- 2"~S2 + + Sn). Заметим, что между tk и Si существует взаимно обратное соответствие. Пусть также gk{sk,... ,Sn,tk) - это ш в степени 2*" (s„ + 2s„ i -h--- + 2"-=Sfc).

На каждой итерации мы, по существу, берем 2"~ пар комплексных чисел (а,/3) и заменяем их числами (а + (0, а - С/?), где С -подходящая степень uj. Следовательно, = cos 4- isin для некоторого в. Если предпочесть упрощения, когда = ±1 или ±г, вся работа сведется к ((п - 3) • 2"" + 2) комплексным умножениям и п 2" комплексным сложениям. Техника упр. 41 может быть использована для уменьшения числа умножений и сложений действительных чисел с помощью операций для комплексных чисел.

Количество умножений комплексных чисел можно уменьшить приблизительно на 25%

без изменения числа сложений, объединяя шаги к и к + 1 для к = 1, 3, Это означает,

что 2"~2 четверок {a,f3,f,6) заменятся выражением

(а + С/3 + + С<5, а + гС/3 - - Кб, а - С/3 + - С<5, а - i0 - СЧ + К&У

Общее число умножений комплексных чисел, когда п - четное, в результате уменьшается до (3n-2)2"--5[2"-V3j.

В этих вычислениях предполагается, что заданные числа F{t) - комплексные. Если F[t) - действительные числа, то /(s) - комплексно-сопряженные к /(2" - s). Таким образом, можно избежать операций, вычисляя только 2" независимых действительных чисел /(0), К/(1), К/(2"- - 1), /(2""), Э/(1), /(2"- - 1). Все вычисления в этом случае могут быть сведены к операциям с 2" действительными числа.ми, если учитывается тот факт, что fk(sn-k+i,... ,Sn,ti,..., tn-k) будут комплексно-сопряженными

к fk{sn-k+l,- • 1вп,<Ь • • -jtn-k), когда (Sl . . . Sn)2 + (sl . . . s„)2 = О ПО МОДуЛЮ 2". ОкОЛО

половины умножений и сложений так же необходимы, как и для комплексных чисел.

[Алгоритм быстрого преобразования Фурье открыт К. Ф. Гауссом в 1805 году и независимо открывался в дальнейшем. Наиболее интересно это сделали Дж. В. Кули (J. W. Cooley) и Дж. У. Тьюки (J. W. Тикеу), Math. Сотр. 19 (1965), 297-301. Его интересная история прослежена Дж. В. Кули, П. А. У. Левисом и П. Д. Уэлчем (J. W. Cooley, Р. А. W. Lewis and P. D. Welch, Proc. IEEE 55 (1967), 1675-1677); M. T. Heideman, D. H. Johnson, and C. S. Burrus, IEEE ASSP Magazine 1,4 (October, 1984), 14-21. Детали, связанные с его применением, обсуждались сотнями авторов; это обсуждение очень кратко изложил Чарлз Ван Лоан (Charles Van Loan, Computational Frameworks for the Fast Fourier Transform (Philadelphia: SIAM, 1992)). Обзор быстрого преобразования Фурье на конечных группах приводится в работе М. Clausen and U. Baum, Fast Fourier IVansforms (Mannheim: Bibliographisches Institut Wissenschaftsverlag, 1993).]