|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 08 Apr 2003 09:52:48
To : Max Alekseyev
Subject : умножения на фиксированную матрицу
--------------------------------------------------------------------------------
Mon Apr 07 2003 12:35, 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>> В общем случае ускорить невозможно.
MA> Есть какой-то отрицательный результат, из которого следует столь
MA> категорическое нет?
Hет. Это только обобщение практического опыта.
Впрочем, для случая единственного и произвольного вектора и матрицы общего
вида доказательство очевидно.
Hевозможно однозначно отобразить матрицу общего вида менее чем на n^2
параметров. А, значит, и операций при умножении будет не меньше, поскольку
произведение будет зависеть от каждого из них.
Для пакета векторов, как уже здесь предлагалось, можно воспользоваться
Штрассеном и т.п. - но люди, реализовывашие его практически, обнаружили
драматическое падение точности - сложение имеет привычку дарить нам
"катастрофическую потерю порядка"...
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
умножения на фиксированную матрицу 