Методы без матриц

В вычислительной математике безматричный метод — это алгоритм решения линейной системы уравнений или задачи на собственные значения , который не хранит матрицу коэффициентов явно, а обращается к матрице, оценивая произведения матрицы и вектора. ^[1] Такие методы могут быть предпочтительными, когда матрица настолько велика, что ее хранение и обработка потребует много памяти и времени вычислений, даже при использовании методов для разреженных матриц . Многие итерационные методы допускают реализацию без матрицы, в том числе:

метод мощности ,
алгоритм Ланцоша , ^[2]
Метод локально-оптимального блочного предобусловленного сопряженного градиента ( LOBPCG ), ^[3]
Координатно-рекуррентный алгоритм Видемана ^[4] и
метод сопряженных градиентов . ^[5]
Методы подпространства Крылова

Распределенные решения также были исследованы с использованием крупнозернистых параллельных программных систем для достижения однородных решений линейных систем. ^[6]

Обычно он используется при решении нелинейных уравнений, таких как уравнения Эйлера в вычислительной гидродинамике . Метод сопряженных градиентов без матриц был применен в нелинейном упругопластическом решателе конечных элементов. ^[7] Решение этих уравнений требует вычисления якобиана , что является дорогостоящим с точки зрения процессорного времени и памяти. Чтобы избежать этих расходов, используются методы без матриц. Чтобы устранить необходимость вычисления якобиана, вместо этого формируется векторное произведение якобиана, которое на самом деле само является вектором. Манипулировать этим вектором и вычислять его проще, чем работать с большой матрицей или линейной системой.

Ссылки

^ Лангвилл, Эми Н.; Мейер, Карл Д. (2006), PageRank Google и не только: наука о рейтингах поисковых систем , Princeton University Press , стр. 40, ISBN 978-0-691-12202-1
^ Копперсмит, Дон (1993), «Решение линейных уравнений над GF(2): алгоритм блочного Ланцоша», Линейная алгебра и ее приложения , 192 : 33–60 , doi : 10.1016/0024-3795(93)90235-G
^ Князев, Эндрю В. (2001). «К оптимальному предобусловленному собственному решателю: локально оптимальный блочно-предобусловленный метод сопряженных градиентов». Журнал SIAM по научным вычислениям . 23 (2): 517– 541. Bibcode :2001SJSC...23..517K. CiteSeerX 10.1.1.34.2862 . doi :10.1137/S1064827500366124.
^ Видеманн, Д. (1986), «Решение разреженных линейных уравнений над конечными полями» (PDF) , IEEE Transactions on Information Theory , 32 : 54–62 , doi :10.1109/TIT.1986.1057137
^ Lamacchia, BA; Odlyzko, AM (1991), "Решение больших разреженных линейных систем над конечными полями", Advances in Cryptology – CRYPT0' 90 , Lecture Notes in Computer Science, т. 537, стр. 109, doi : 10.1007/3-540-38424-3_8 , ISBN 978-3-540-54508-8
^ Kaltofen, E.; Lobo, A. (1996), "Распределенное безматричное решение больших разреженных линейных систем над конечными полями", Algorithmica , т. 24, № 3–4 , стр. 311–348 , CiteSeerX 10.1.1.17.7470 , doi :10.1007/PL00008266, S2CID 13305650
^ Prabhune, Bhagyashree C.; Krishnan, Suresh (4 марта 2020 г.). "Быстрый безматричный упругопластический решатель для прогнозирования остаточных напряжений в аддитивном производстве". Computer Aided Design . 123 : 102829. doi : 10.1016/j.cad.2020.102829 .

Эта статья по прикладной математике – заглушка . Вы можете помочь Википедии, расширив ее.

[1] Лангвилл, Эми Н.; Мейер, Карл Д. (2006), PageRank Google и не только: наука о рейтингах поисковых систем , Princeton University Press , стр. 40, ISBN 978-0-691-12202-1

[2] Копперсмит, Дон (1993), «Решение линейных уравнений над GF(2): алгоритм блочного Ланцоша», Линейная алгебра и ее приложения , 192 : 33–60 , doi : 10.1016/0024-3795(93)90235-G

[3] Князев, Эндрю В. (2001). «К оптимальному предобусловленному собственному решателю: локально оптимальный блочно-предобусловленный метод сопряженных градиентов». Журнал SIAM по научным вычислениям . 23 (2): 517– 541. Bibcode :2001SJSC...23..517K. CiteSeerX 10.1.1.34.2862 . doi :10.1137/S1064827500366124.

[4] Видеманн, Д. (1986), «Решение разреженных линейных уравнений над конечными полями» (PDF) , IEEE Transactions on Information Theory , 32 : 54–62 , doi :10.1109/TIT.1986.1057137

[5] Lamacchia, BA; Odlyzko, AM (1991), "Решение больших разреженных линейных систем над конечными полями", Advances in Cryptology – CRYPT0' 90 , Lecture Notes in Computer Science, т. 537, стр. 109, doi : 10.1007/3-540-38424-3_8 , ISBN 978-3-540-54508-8

[6] Kaltofen, E.; Lobo, A. (1996), "Распределенное безматричное решение больших разреженных линейных систем над конечными полями", Algorithmica , т. 24, № 3–4 , стр. 311–348 , CiteSeerX 10.1.1.17.7470 , doi :10.1007/PL00008266, S2CID 13305650

[7] Prabhune, Bhagyashree C.; Krishnan, Suresh (4 марта 2020 г.). "Быстрый безматричный упругопластический решатель для прогнозирования остаточных напряжений в аддитивном производстве". Computer Aided Design . 123 : 102829. doi : 10.1016/j.cad.2020.102829 .