Безматричные методы - Matrix-free methods

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

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

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

использованная литература

  1. ^ Лэнгвилл, Эми Н.; Мейер, Карл Д. (2006), Google PageRank и не только: наука о рейтинге в поисковых системах, Princeton University Press, п. 40, ISBN  978-0-691-12202-1
  2. ^ Копперсмит, Дон (1993), "Решение линейных уравнений над GF (2): алгоритм Блока Ланцоша", Линейная алгебра и ее приложения, 192: 33–60, Дои:10.1016 / 0024-3795 (93) 90235-Г
  3. ^ Князев, Андрей В. (2001). "На пути к оптимальному предварительно обусловленному собственному вычислителю: локально оптимальный блочный предобусловленный метод сопряженных градиентов". Журнал SIAM по научным вычислениям. 23 (2): 517–541. CiteSeerX  10.1.1.34.2862. Дои:10.1137 / S1064827500366124.
  4. ^ Видеманн, Д. (1986), «Решение разреженных линейных уравнений над конечными полями» (PDF), IEEE Transactions по теории информации, 32: 54–62, Дои:10.1109 / TIT.1986.1057137
  5. ^ Lamacchia, B.A .; Одлызко, А. М. (1991), "Решение больших разреженных линейных систем над конечными полями", Достижения в криптологии-CRYPT0 '90, Конспект лекций по информатике, 537, п. 109, Дои:10.1007/3-540-38424-3_8, ISBN  978-3-540-54508-8
  6. ^ Kaltofen, E .; Лобо, А. (1996), "Распределенное безматричное решение больших разреженных линейных систем над конечными полями", Алгоритмика, 24 (3–4), стр. 311–348, CiteSeerX  10.1.1.17.7470, Дои:10.1007 / PL00008266
  7. ^ Prabhune, Bhagyashree C .; Кришнан, Суреш (4 марта 2020 г.). «Быстрая безматричная программа для расчета эластопластов для прогнозирования остаточных напряжений в аддитивном производстве». Системы автоматизированного проектирования. 123: 102829. Дои:10.1016 / j.cad.2020.102829.