Решение СЛАУ

From

Ilya Rogov (2:5030/1334.1024)

To

Evgenij Masherov

Date

2003-01-18T01:21:15Z

Area

RU.ALGORITHMS

    Привет тебе, Evgenij, с того света от Ильи.

 Давным-давно, 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. Ну, вот у Вас задача. В
 EM> которой Вам нужно обратить матрицу 1000х1000. Операций соответственно
 EM> будет 10^9. Положим, что исходно числа не более чем трехразрядные.
 EM> Тогда в выкладках у Вас будут числа порядка 10^(3*10^9) в количестве
 EM> 2*10^6... Лично мне захочется использовать арифметику обычную, с
 EM> плавающей точкой. Ну, может, еще применю итеративное уточнение...

   1. Чегой-то я не совсем понял твою хитрую запись этого хитрого тождества. Да и с разрядностью чисел ты перепутал ...
   2. Никто не собирается решать разреженную матрицу 1000х1000 Гауссом. Я не   уверен, что речь шла о ТАКИХ размерностях.

 EM> Угу. При этом все определители считая по определению определителя.
 EM> Поскольку в разреженной матрице много нулевых элементов, для
 EM> большинства потребуется лишь сравнение с нулем. И мы обойдемся всего
 EM> лишь 1000!=4,02387260077093773543702433923e+2567 операциями...

   А что, детерминант СИЛЬНО разреженной матрицы мы можем считать только по рекурсивному определению ?? Смеха ради, попробую придумать методу ...

                                                        Ilya Rogov
... Бредить помогали вопли моих соседей
---
 * Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)