ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   07 Apr 2003  21:27:00
 To : Max Alekseyev
 Subject : умножения на фиксированную матрицу
 -------------------------------------------------------------------------------- 
 

 Mon Apr 07 2003 02:13, Max Alekseyev wrote to All:
 
  MA> Предположим, что задана фиксированная матрица M размера nxn и планируется
  MA> вычислять произведения M*x для различных векторов x.
 
  MA> Вычисление в лоб требует порядка n^2 элементарных операций. Возможно ли
  MA> уменьшить это число путем каких-то предвычислений?
 
  MA> Т.е. планируется вычислять большое количество произведений M*x для
  MA> различных x, и очень бы хотелось на каждое произведение затрачивать как
  MA> можно меньше операций.
 
  Только для специальной структуры матрицы М. В общем случае ускорить
 невозможно.
 А, скажем, для M(i,j)=m((i-j) mod n) можно за O(n log n)
 Или для разреженных...
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    умножения на фиксированную матрицу   Max Alekseyev   07 Apr 2003 02:13:28   умножения на фиксированную матрицу   Evgenij Masherov   07 Apr 2003 21:27:00   умножения на фиксированную матрицу   Max Alekseyev   07 Apr 2003 12:35:42   умножения на фиксированную матрицу   Evgenij Masherov   08 Apr 2003 09:52:48   умножения на фиксированную матрицу   Max Alekseyev   08 Apr 2003 16:50:40   умножения на фиксированную матрицу   Evgenij Masherov   09 Apr 2003 10:03:10   умножения на фиксированную матрицу   Konstantin Polyakov   09 Apr 2003 19:33:57   умножения на фиксированную матрицу   Evgenij Masherov   09 Apr 2003 20:31:14   KDD CUP 2003   Trunov   23 Apr 2003 17:00:06   yмножения на фиксиpованнyю матpицy   Wowa Savin   25 Apr 2003 21:07:07   yмножения на фиксиpованнyю матpицy   Aleksey Loginov   08 Apr 2003 18:34:55