Аннотация:
Для предобусловливания симметричной положительно-определенной разреженной матрицы рассматривается ее приближенная обратная, представленная в виде произведения двух взаимно сопряженных разреженных треугольных матриц. Таким образом, решение соответствующей системы линейных алгебраических уравнений (СЛАУ) предобусловленным методом сопряженных градиентов (МСГ) требует лишь выполнения элементарных векторных операций, а также операций умножения разреженной матрицы на вектор. Описан и исследован метод построения указанного предобусловливателя при фиксированной структуре разреженности треугольного множителя, оптимального в смысле минимизации К-числа обусловленности предобусловленной матрицы. При этом существенно уменьшить долю операций скалярного произведения (при незначительном изменении суммарного числа арифметических операций) можно за счет дополнительного использования полиномиального предобусловливания на основе чебышёвских многочленов. Обсуждается возможность эффективной массивно-параллельной реализации полученного метода решения СЛАУ. Для последовательного прототипа метода приводятся результаты расчетов 56 тестовых задач из коллекции университета Флориды (отличающихся большими размерами и плохой обусловленностью), свидетельствующие о его высокой надежности и низких вычислительных затратах. Библ. 27.
Образец цитирования:
И. Е. Капорин, “Использование полиномов Чебышёва и приближенного обратного треугольного разложения для предобусловливания метода сопряженных градиентов”, Ж. вычисл. матем. и матем. физ., 52:2 (2012), 179–204; Comput. Math. Math. Phys., 52:2 (2012), 169–193
\RBibitem{Kap12}
\by И.~Е.~Капорин
\paper Использование полиномов Чебышёва и приближенного обратного треугольного разложения для предобусловливания метода сопряженных градиентов
\jour Ж. вычисл. матем. и матем. физ.
\yr 2012
\vol 52
\issue 2
\pages 179--204
\mathnet{http://mi.mathnet.ru/zvmmf9647}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2953307}
\zmath{https://zbmath.org/?q=an:1245.65035}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2012CMMPh..52..169K}
\elib{https://elibrary.ru/item.asp?id=17353052}
\transl
\jour Comput. Math. Math. Phys.
\yr 2012
\vol 52
\issue 2
\pages 169--193
\crossref{https://doi.org/10.1134/S0965542512020091}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000303535300001}
\elib{https://elibrary.ru/item.asp?id=17977779}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84857601550}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf9647
https://www.mathnet.ru/rus/zvmmf/v52/i2/p179
Эта публикация цитируется в следующих 24 статьяx:
О. Ю. Милюкова, “Некоторые способы параллельной реализации метода сопряженных градиентов с неявным факторизованным предобусловливателем”, Матем. моделирование, 36:2 (2024), 174–196; O. Yu. Milyukova, “Some ways of parallel implementation of the conjugate gradient method with an implicit factorized preconditioner”, Math. Models Comput. Simul., 16:4 (2024), 638–653
О. Ю. Милюкова, “Сочетание числовых и структурных подходов в параллельном методе предобусловливания неполного треугольного разложения первого порядка”, Препринты ИПМ им. М. В. Келдыша, 2024, 075, 28 с.
О. Ю. Милюкова, “MPI+OpenMP реализация метода сопряженных градиентов с факторизованным предобусловливателем на основе использования переупорядочения узлов сетки”, Препринты ИПМ им. М. В. Келдыша, 2023, 018, 29 с.
О. Ю. Милюкова, “Способы MPI+OpenMP реализации метода сопряженных градиентов с предобусловливателем IC(0) на основе использования переупорядочения узлов сетки”, Препринты ИПМ им. М. В. Келдыша, 2023, 035, 32 с.
О. Ю. Милюкова, “Параллельная реализация метода сопряженных градиентов с предобусловливателем IC1 на основе использования переупорядочения узлов сетки”, Препринты ИПМ им. М. В. Келдыша, 2023, 061, 28 с.
L. Bergamaschi, M. Ferronato, G. Isotton, C. Janna, A. Martínez, “Parallel matrix-free polynomial preconditioners with application to flow simulations in discrete fracture networks”, Computers & Mathematics with Applications, 146 (2023), 60
О. Ю. Милюкова, “Способы MPI+OpenMP реализации метода сопряженных градиентов с предобусловливанием блочного неполного обратного треугольного разложения IC1”, Препринты ИПМ им. М. В. Келдыша, 2022, 002, 30 с.
О. Ю. Милюкова, “MPI+OpenMP реализация метода сопряженных градиентов с предобусловливателем IC(0) на основе использования переупорядочения узлов сетки”, Препринты ИПМ им. М. В. Келдыша, 2022, 063, 32 с.
О. Ю. Милюкова, “MPI+OpenMP реализация метода сопряженных градиентов с факторизованными неявными предобусловливателями”, Матем. моделирование, 33:10 (2021), 19–38; O. Yu. Milyukova, “MPI+OpenMP parallel implementation of conjugate gradient method with factored implicit preconditioners”, Math. Models Comput. Simul., 14:3 (2022), 367–380
О. Ю. Милюкова, “MPI+OpenMPI реализация метода сопряженных градиентов c предобусловливателем блочного неполного обратного треугольного разложения IC2S и IC1”, Препринты ИПМ им. М. В. Келдыша, 2021, 048, 32 с.
Bergamaschi L., Calomardo A.M., “Parallel Newton-Chebyshev Polynomial Preconditioners For the Conjugate Gradient Method”, Comput. Math. Methods, 3:6 (2021), e1153
О. Ю. Милюкова, “MPI+OpenMPI реализация метода сопряженных градиентов с факторизованным предобусловливателем”, Препринты ИПМ им. М. В. Келдыша, 2020, 031, 22 с.
О. Ю. Милюкова, “MPI+OpenMP реализация метода сопряженных градиентов с предобусловливателем блочного Якоби IC1”, Препринты ИПМ им. М. В. Келдыша, 2020, 083, 28 с.
Igor Kaporin, Lecture Notes in Computer Science, 12422, Optimization and Applications, 2020, 184
Sadkane M., Touhami A., “Chebstablkcg: a Block Variant of Chebfiltercg”, Numer. Linear Algebr. Appl., 26:2 (2019), e2227
И. Е. Капорин, О. Ю. Милюкова, “MPI+OpenMP параллельная реализация метода сопряженных градиентов с некоторыми явными предобусловливателями”, Препринты ИПМ им. М. В. Келдыша, 2018, 008, 28 с.
M. Sadkane, A. Touhami, “Convergence analysis of the ChebFilterCG algorithm”, Numer. Linear Algebr. Appl., 24:3 (2017)
И. Е. Капорин, О. Ю. Милюкова, “Неполное обратное треугольное разложение в параллельных алгоритмах предобусловленного метода сопряженных градиентов”, Препринты ИПМ им. М. В. Келдыша, 2017, 037, 28 с.
О. Ю. Милюкова, “Сочетание числовых и структурных подходов к построению неполного треугольного разложения второго порядка в параллельных методах предобусловливания”, Ж. вычисл. матем. и матем. физ., 56:5 (2016), 711–729; O. Yu. Milyukova, “Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods”, Comput. Math. Math. Phys., 56:5 (2016), 699–716
О. Ю. Милюкова, “Об одном параллельном варианте метода неполного треугольного разложения второго порядка”, Матем. моделирование, 28:12 (2016), 107–121; O. Yu. Milyukova, “About one parallel version of the 2nd order incomplete triangular factorization”, Math. Models Comput. Simul., 11:2 (2019), 309–320
Цитирование в формате AMSBIB
Обратная связь: