ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Konstantin Polyakov                  2:5030/542.251 09 Apr 2003  19:33:57
 To : Evgenij Masherov
 Subject : умножения на фиксированную матрицу
 -------------------------------------------------------------------------------- 
 

 
  MA>> Кстати, а что насчет матрицы M(i,j)=(i-j)^(-1) mod n при i<>j, и
  MA>> M(i,i)=0 ?
 
  EM> Строки матрицы получаются циклическим сдвигом. Поэтому задача умножения
  EM> строк матриц на столбец сводится к задаче вычисления циклической свертки
  EM> первой
  EM> строки и данного столбца. Ее можно делать через Фурье.
  EM> Фурье от строки, Фурье от столбца, перемножаем, обратное Фурье - и вуаля.
  EM> Трижды по O(n log n)
 
 Как в этом алгоpитме обстоят дела с ошибками пpи вычислениях с конечной
 точностью? (Видел заpубежные pаботы по матpичным вычислениям, котоpые
 показывают, что многие superfast алгоpитмы численно неустойчивы).
 
  С уважением, Konstantin Polyakov.
 
 --- GoldED 3.0.1
  * Origin: Судя по всему, все возможно ...  (2:5030/542.251)
 
 

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

Тема:    Автор:    Дата:    умножения на фиксированную матрицу   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