|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 07 Apr 2003 12:35:42
To : Evgenij Masherov
Subject : умножения на фиксированную матрицу
--------------------------------------------------------------------------------
Replying to a message of Evgenij Masherov to Max Alekseyev:
MA>> Предположим, что задана фиксированная матрица M размера nxn и
MA>> планируется вычислять произведения M*x для различных векторов x.
MA>> Вычисление в лоб требует порядка n^2 элементарных операций. Возможно
MA>> ли уменьшить это число путем каких-то предвычислений?
MA>> Т.е. планируется вычислять большое количество произведений M*x для
MA>> различных x, и очень бы хотелось на каждое произведение затрачивать
MA>> как можно меньше операций.
EM> Только для специальной структуры матрицы М.
EM> В общем случае ускорить невозможно.
Есть какой-то отрицательный результат, из которого следует столь категорическое
нет?
EM> А, скажем, для M(i,j)=m((i-j) mod n) можно за O(n log n)
EM> Или для разреженных...
Это понятно, но меня интересует общий случай.
Regards, ш.ш
Max ~
--- OS/2 Uptime: 1d 14h 44m 14s 351ms
* Origin: Параллельно пути черный спутник летит... (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
