Безматричные методы
В вычислительной математике безматричный метод — это алгоритм решения линейной системы уравнений или задачи собственных значений , который не сохраняет матрицу коэффициентов явно, но получает доступ к матрице путем оценки матрично-векторных произведений. [1] Такие методы могут быть предпочтительнее, когда матрица настолько велика, что ее хранение и манипулирование ею будут требовать больших затрат памяти и вычислительного времени, даже при использовании методов для разреженных матриц . Многие итеративные методы допускают реализацию без матрицы, в том числе:
- силовой метод ,
- алгоритм Ланцоша , [2]
- Локально оптимальный блочный метод сопряженных градиентов с предварительным условием ( LOBPCG ), [3]
- Алгоритм рекурсии координат Видемана, [4] и
- метод сопряженных градиентов . [5]
- Krylov subspace methods
Распределенные решения также исследовались с использованием крупнозернистых параллельных программных систем для достижения однородных решений линейных систем. [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. CiteSeerX 10.1.1.34.2862 . дои : 10.1137/S1064827500366124 .
- ^ Видеманн, Д. (1986), «Решение разреженных линейных уравнений над конечными полями» (PDF) , IEEE Transactions on Information Theory , 32 : 54–62, doi : 10.1109/TIT.1986.1057137
- ^ Ламаккья, Бакалавр; Одлизко, А.М. (1991), «Решение больших разреженных линейных систем над конечными полями», Достижения в криптологии - CRYPT0'90 , Конспекты лекций по информатике, том. 537, с. 109, номер домена : 10.1007/3-540-38424-3_8 , ISBN 978-3-540-54508-8
- ^ Кальтофен, Э.; Лобо, А. (1996), "Распределенное безматричное решение больших разреженных линейных систем над конечными полями", Algorithmica , vol. 24, нет. 3–4, стр. 311–348, CiteSeerX 10.1.1.17.7470 , doi : 10.1007/PL00008266 , S2CID 13305650
- ^ Прабхун, Бхагьяшри К.; Кришнан, Суреш (4 марта 2020 г.). «Быстрый безматрицный упругопластический решатель для прогнозирования остаточных напряжений в аддитивном производстве» . Компьютерное проектирование . 123 : 102829. doi : 10.1016/j.cad.2020.102829 .
 | Эта прикладной математике, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |