ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilya Rogov                           2:5030/1334.1024 18 Jan 2003  02:21:15
 To : Evgenij Masherov
 Subject : Решение СЛАУ
 -------------------------------------------------------------------------------- 
 

  Давным-давно, 17 Jan 03 09:37, когда земля была ещё тёпленькая
  и по ней бегали мамонты, Evgenij Masherov и Ilya Rogov говорили про Решение
 СЛАУ:
 
  EM> 0. Это метод Штрассена. Описан во втором томе Кнута, п.4.6.4
  EM> применительно к умножению матриц. Основан на итеративном применении
  EM> тождества (a b )(A  -C)_(  (a+d)(A+D)-(b+d)(B+D)-d(A-B)-(a-b)D
  EM> (a-b)D-a(D-C)  ) (c d )(-B -D)-(  (d-c)A-d(A-B)
  EM> (a+d)(A+D)-(a+c)(A+C)-a(D-C)-(d-c)A   ) Обобщение на задачу обращения
  EM> матриц можно найти у Ахо, Хопкрофт, Ульман. 1. Hу, вот у Вас задача. В
  EM> которой Вам нужно обратить матрицу 1000х1000. Операций соответственно
  EM> будет 10^9. Положим, что исходно числа не более чем трехразрядные.
  EM> Тогда в выкладках у Вас будут числа порядка 10^(3*10^9) в количестве
  EM> 2*10^6... Лично мне захочется использовать арифметику обычную, с
  EM> плавающей точкой. Hу, может, еще применю итеративное уточнение...
 
    1. Чегой-то я не совсем понял твою хитрую запись этого хитрого тождества. Да 
 и с разрядностью чисел ты перепутал ...
    2. Hикто не собирается решать разреженную матрицу 1000х1000 Гауссом. Я не  
 уверен, что речь шла о ТАКИХ размерностях.
 
  EM> Угу. При этом все определители считая по определению определителя.
  EM> Поскольку в разреженной матрице много нулевых элементов, для
  EM> большинства потребуется лишь сравнение с нулем. И мы обойдемся всего
  EM> лишь 1000!=4,02387260077093773543702433923e+2567 операциями...
 
    А что, детерминант СИЛЬHО разреженной матрицы мы можем считать только по
 рекурсивному определению ?? Смеха ради, попробую придумать методу ...
 
                                                         Ilya Rogov
 ... Бредить помогали вопли моих соседей
 ---
  * Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)
 
 

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

Тема:    Автор:    Дата:    Решение СЛАУ   Evgenij Masherov   13 Jan 2003 11:01:36   Решение СЛАУ   Andrew Kuksov   13 Jan 2003 14:42:40   Re: Решение СЛАУ   Maxim Balagansky   14 Jan 2003 09:46:16   Re: Решение СЛАУ   Kropov Valentine   18 Jan 2003 00:26:14   Re^2: Решение СЛАУ   Maxim Balagansky   20 Jan 2003 11:12:36   RE: Re[2]: Решение СЛАУ   Kropov Valentine   21 Jan 2003 10:47:53   Re: Решение СЛАУ   Sergei Katkovsky   22 Jan 2003 12:19:25   Решение СЛАУ   Evgenij Masherov   14 Jan 2003 10:27:25   Решение СЛАУ   Andrew Kuksov   14 Jan 2003 20:58:24   Решение СЛАУ   Vladimir Vassilevsky   15 Jan 2003 04:18:38   Решение СЛАУ   Evgenij Masherow   15 Jan 2003 11:47:07   Решение СЛАУ   Vladimir Vassilevsky   15 Jan 2003 18:33:59   Решение СЛАУ   Evgenij Masherov   15 Jan 2003 20:35:33   Решение СЛАУ   Evgenij Masherov   17 Jan 2003 11:34:53   Решение СЛАУ   Vladimir Vassilevsky   17 Jan 2003 18:00:59   Re: Решение СЛАУ   Sergei Katkovsky   14 Jan 2003 15:52:34   Re: Решение СЛАУ   Sergej Tarasov   14 Jan 2003 21:07:30   Re: Решение СЛАУ   Sergei Katkovsky   14 Jan 2003 21:36:35   Re^2: Решение СЛАУ   Maxim Balagansky   15 Jan 2003 09:50:10   Re: Решение СЛАУ   Sergei Katkovsky   15 Jan 2003 17:16:42   Re: Решение СЛАУ   Sergej Tarasov   16 Jan 2003 00:45:11   Re: Решение СЛАУ   Sergei Katkovsky   16 Jan 2003 02:28:41   Re^2: Решение СЛАУ   Maxim Balagansky   16 Jan 2003 12:39:20   Re: Решение СЛАУ   Sergei Katkovsky   16 Jan 2003 13:06:49   Re^2: Решение СЛАУ   Maxim Balagansky   17 Jan 2003 11:09:20   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:41:32   Re^2: Решение СЛАУ   Maxim Balagansky   16 Jan 2003 12:37:00   Re^2: Решение СЛАУ   Sergej Tarasov   17 Jan 2003 01:03:42   Re^3: Решение СЛАУ   Maxim Balagansky   17 Jan 2003 11:18:30   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:43:36   Re^2: Решение СЛАУ   Maxim Balagansky   20 Jan 2003 11:26:12   Re: Решение СЛАУ   Sergei Katkovsky   20 Jan 2003 11:04:34   Re^2: Решение СЛАУ   Maxim Balagansky   21 Jan 2003 10:13:50   Re: Решение СЛАУ   Sergei Katkovsky   21 Jan 2003 07:17:14   Re^2: Решение СЛАУ   Maxim Balagansky   22 Jan 2003 10:29:24   Re: Решение СЛАУ   Sergei Katkovsky   22 Jan 2003 12:23:31   Re^2: Решение СЛАУ   Maxim Balagansky   23 Jan 2003 10:08:22   Re: Решение СЛАУ   Sergei Katkovsky   27 Jan 2003 03:57:38   Re^2: Решение СЛАУ   Maxim Balagansky   24 Jan 2003 14:54:16   Re: Решение СЛАУ   Sergei Katkovsky   27 Jan 2003 04:00:09   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:40:29   Re^2: Решение СЛАУ   Maxim Balagansky   16 Jan 2003 12:28:12   Re: Решение СЛАУ   Sergei Katkovsky   16 Jan 2003 13:07:20   Re^2: Решение СЛАУ   Maxim Balagansky   17 Jan 2003 10:40:52   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:41:32   Решение СЛАУ   Ilya Rogov   17 Jan 2003 04:01:50   Решение СЛАУ   Evgenij Masherov   17 Jan 2003 10:37:40   Решение СЛАУ   Ilya Rogov   18 Jan 2003 02:21:15   Решение СЛАУ   Evgenij Masherov   18 Jan 2003 10:35:45   Решение СЛАУ   Konstantin Polyakov   14 Jan 2003 20:14:35