|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 09 Apr 2003 20:31:14
To : Konstantin Polyakov
Subject : умножения на фиксированную матрицу
--------------------------------------------------------------------------------
Wed Apr 09 2003 19:33, Konstantin Polyakov wrote to Evgenij Masherov:
MA>>> Кстати, а что насчет матрицы M(i,j)=(i-j)^(-1) mod n при i<>j, и
MA>>> M(i,i)=0 ?
EM>> Строки матрицы получаются циклическим сдвигом. Поэтому задача умножения
EM>> строк матриц на столбец сводится к задаче вычисления циклической свертки
EM>> первой
EM>> строки и данного столбца. Ее можно делать через Фурье.
EM>> Фурье от строки, Фурье от столбца, перемножаем, обратное Фурье - и
EM>> вуаля. Трижды по O(n log n)
KP> Как в этом алгоpитме обстоят дела с ошибками пpи вычислениях с конечной
KP> точностью? (Видел заpубежные pаботы по матpичным вычислениям, котоpые
KP> показывают, что многие superfast алгоpитмы численно неустойчивы).
Полагаю, превосходно. Все преобразования ортогональны.
Впрочем, рекомендовал бы провести численный эксперимент.
Скажем, вычисляя трижды - с двойной точностью стандартным образом, как эталон,
с одинарной стандартным, как базу для сравнения и описанным - для собственно
сравнения. Вектора брать случайно или из реальной задачи.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
