|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 09 Apr 2003 10:03:10
To : Max Alekseyev
Subject : умножения на фиксированную матрицу
--------------------------------------------------------------------------------
Tue Apr 08 2003 16:50, Max Alekseyev wrote to Evgenij Masherov:
MA>>> Предположим, что задана фиксированная матрица M размера nxn и
MA>>> планируется вычислять произведения M*x для различных векторов x.
MA>>> Вычисление в лоб требует порядка n^2 элементарных операций. Возможно
MA>>> ли уменьшить это число путем каких-то предвычислений?
MA>>> Т.е. планируется вычислять большое количество произведений M*x для
MA>>> различных x, и очень бы хотелось на каждое произведение затрачивать
MA>>> как можно меньше операций.
EM>> Только для специальной структуры матрицы М. В общем случае ускорить
EM>> невозможно. А, скажем, для M(i,j)=m((i-j) mod n) можно за O(n log n)
EM>> Или для разреженных...
MA> Кстати, а что насчет матрицы M(i,j)=(i-j)^(-1) mod n при i<>j, и M(i,i)=0
MA> ?
Строки матрицы получаются циклическим сдвигом. Поэтому задача умножения строк
матриц на столбец сводится к задаче вычисления циклической свертки первой
строки и данного столбца. Ее можно делать через Фурье.
Фурье от строки, Фурье от столбца, перемножаем, обратное Фурье - и вуаля.
Трижды по O(n log n)
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
