|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 08 Apr 2003 16:50:40
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> невозможно. А, скажем, для M(i,j)=m((i-j) mod n) можно за O(n log n)
EM> Или для разреженных...
Кстати, а что насчет матрицы M(i,j)=(i-j)^(-1) mod n при i<>j, и M(i,i)=0 ?
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
