Отправить статью по E-mail 
К-ОПТИМАЛЬНЫЕ ПРЕДОБУСЛАВЛИВАТЕЛИ НА ОСНОВЕ ПРИБЛИЖЕНИЯ ОБРАТНЫХ МАТРИЦ
- Авторы: Оселедец И.В1,2,3, Муравлева Е.А4,2
-
Учреждения:
- Институт искусственного интеллекта (AIRI)
- Сколковский институт науки и технологий
- ИВМ РАН
- Центр AI для науки, Сбербанк
- Выпуск: Том 65, № 7 (2025)
- Страницы: 1143-1155
- Раздел: ОБЩИЕ ЧИСЛЕННЫЕ МЕТОДЫ
- URL: https://bakhtiniada.ru/0044-4669/article/view/304081
- DOI: https://doi.org/10.31857/S0044466925070063
- EDN: https://elibrary.ru/JXYARI
- ID: 304081
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Рассматривается задача построения предобуславливателей специального вида для решения систем линейных алгебраических уравнений. Предложен новый подход к построению предобуславливателей, основанный на минимизации K-числа обусловленности для матрицы A−1P, где A — исходная матрица системы, P — предобуславливатель. Доказано, что для циркулянтных матриц такой подход эквивалентен построению оптимального циркулянта Чэна для обратной матрицы. Проведены численные эксперименты на серии тестовых задач с тёплицевыми матрицами, показывающие, что предложенный подход позволяет существенно уменьшить число итераций метода сопряженных градиентов по сравнению с классическим подходом. Полученные результаты открывают новые возможности для построения эффективных предобуславливателей в других классах матриц.
Ключевые слова
Об авторах
И. В Оселедец
Институт искусственного интеллекта (AIRI); Сколковский институт науки и технологий; ИВМ РАН
Email: oseledets@uiri.net
Москва, Россия; Москва, Россия ; Москва, Россия
Е. А Муравлева
Центр AI для науки, Сбербанк; Сколковский институт науки и технологий
Email: EdnaMuravleva@sberbank.ru
Москва, Россия; Москва, Россия
Список литературы
- Häusner P., Juscafresa A.N., Sjölund J. Learning incomplete factorization preconditioners for GMRES // arXiv preprint arXiv:2409.08262, 2024.
- Häusner P., Öktem O., Sjölund J. Neural incomplete factorization: learning preconditioners for the conjugate gradient method // arXiv preprint arXiv:2305.16368, 2023.
- Trifonov V., Rudikov A., Iliev O., Oseledets I., Muravleva E. Learning from linear algebra: A graph neural network approach to preconditioner design for conjugate gradient solvers // arXiv preprint arXiv:2405.15557, 2024.
- Katrutsa A., Daulbaev T., Oseledets I. Black-box learning of multigrid parameters // J. Comput. Appl. Math. 2020. V. 368. P. 112524.
- Gelfand I. Normierte Ringe // Marew. c6. 1941. Т. 9. № 1. С. 3–24.
- Kozyakin V.S. On accuracy of approximation of the spectral radius by the Gelfand formula // Linear Algebra Appl. 2009. V. 431. № 11. Р. 2134–2141.
- Hutchinson M.F. Astochastic estimator of the trace of the influence matrix for Laplacian smoothing splines // Comm. Statist. Simulation Comput. 1989. V. 18. № 3. Р. 1059–1076.
- Chan R.H.F., Jin X.Q. An introduction to iterative Toeplitz solvers // SIAM, 2007.
- Chan T.F. An optimal circulant preconditioner for Toeplitz systems // SIAM J. Sci. Stat. Comput. 1988. V. 9. № 4. Р. 766–771.
- Tyrhyshnikov E.E. Optimal and superoptimal circulant preconditioners // SIAM J. Matrix Anal. Appl. 1992. № 13. № 2. Р. 459–473.
- Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method // Numer. Linear Algebra Appl. 1994. V. 1. № 2. P. 179–210.
- Kaporin I. Superlinear convergence in minimum residual iterations // Numer. Linear Algebra Appl. 2005. V. 12. № 5–6. P. 453–470.
- Kaporin I.E. Preconditioning of the method of conjugate gradients for solving discrete analogues of differential problems // Differ. Uravn. 1990. V. 26. № 7. P. 1225–1236.
- Serra Capizzano S., Tyryshnikov E.E. Any circulant-like preconditioner for multilevel matrices is not superlinear // SIAM J. Matrix Anal. Appl. 2000. V. 21. № 2. P. 431–439.
- Kanopuu H.E. Использование полиномов Чебышёва и приближенного обратного треугольного разложения для предобусловливания метода сопряженных градиентов // Ж. вычисл. матем. и матем. физ. 2012. Т. 52. № 2. С. 179–204.
- Kanopuu H.E., Munoocoa O.IO. Неполное обратное треугольное разложение в параллельных алгоритмах предобусловленного метода сопряженных градиентов // Препринты ИПМ им. М.В. Келдыша. 2017. С. 37–28.
- Oseledets I., Tyryshnikov E. A unifying approach to the construction of circulant preconditioners // Linear Algebra Appl. 2006. V. 418. № 2–3. P. 435–449.
- Tilli P. A note on the spectral distribution of Toeplitz matrices // Linear Multilinear Algebra. 1998. V. 45. № 2–3. P. 147–159.
- Tyryshnikov E.E. A unifying approach to some old and new theorems on distribution and clustering // Linear Algebra Appl. 1996. V. 232. P. 1–43.
Дополнительные файлы
