Анализ и реализация последовательных и параллельных алгоритмов решения СЛАУ на подпространствах Крылова тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Баландин, Михаил Юрьевич
- Специальность ВАК РФ05.13.16
- Количество страниц 156
Оглавление диссертации кандидат физико-математических наук Баландин, Михаил Юрьевич
Введение
Глава 1. Последовательные и параллельные пакеты для решения СЛАУ
1.1 Концепции создания программного обеспечения для решения задач линейной алгебры
1.2 Обзор существующих последовательных пакетов решения СЛАУ
1.3 Параллельное программное обеспечение
1.3.1 Классификация и краткая характеристика многопроцессорных вычислительных систем
1.3.2 Основные проблемы параллелизации существующего программного обеспечения
1.3.3 Эффективность параллельных программ и способы ее оценивания
Глава 2. Решение СЛАУ с плотными матрицами; класс методов А.А.Абрамова
2.1 Введение
2.2 Обозначения
2.3 Построение класса методов и его геометрическая интерпретация
2.3.1 Метод АВК
2.3.2 МетодАВШОЯТ
Оценка точности методом возмущений
Проблема критерия останова
2.4 Связь класса абрамовских методов с АВ8-методами
2.5 Параллельная реализация методов абрамовского класса
2.5.1 Общие соображения о реализации на многопроцессорных системах
2.5.2 Требования к памяти и вычислительная сложность.
2.5.3 Параллельные алгоритмы.
2.5.4 Оценка эффективности параллельных алгоритмов и результаты численных экспериментов
Глава 3. Решение СЛАУ с разреженными несимметричными матрицами.
3.1 Введение
3.2 Особенности СЛАУ, возникающих при решении задач методами конечных элементов и конечных объемов
3.3 Обозначения
3.4 Методы, используемые при решении несимметричных
3.4.1 ОМЯЕ8 и его модификации
Экстремальные случаи выбора размерности подпространства Крылова
3.4.2 ЫСв
3.5 Проблема предобус ловливания и ускорения сходимости при решении конечноэлементных и конечнообъемных задач
3.6 Параллельные реализации
3.6.1 Общие соображения о реализации на многопроцессорных системах
3.6.2 Требования к памяти и вычислительная сложность.
3.6.3 Особенности работы со СЛАУ в разреженном строчном формате на многопроцессорных системах
3.6.4 Параллельный алгоритм ОМКЕБ
3.6.5 Оценка эффективности параллельного алгоритма и результаты численных экспериментов.
3.6.6 Эффект ограничения асимптотического ускорения в параллельной реализации вМЮ^
Глава 4. Программный пакет ЫпРаг
4.1 Общая характеристика пакета
4.2 Особенности программной реализации
4.3 Пример использования в физическом приложении
Рекомендованный список диссертаций по специальности «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», 05.13.16 шифр ВАК
Методы и программные средства организации эффективных вычислений для расчета электронной структуры больших молекулярных систем2012 год, кандидат технических наук Чернецов, Андрей Михайлович
Конечноэлементное моделирование гармонических электромагнитных полей2000 год, кандидат технических наук Рояк, Светлана Хаимовна
Предобусловливание итерационных методов решения систем линейных алгебраических уравнений2011 год, доктор физико-математических наук Капорин, Игорь Евгеньевич
Методы разработки параллельных программ на основе машинного обучения2009 год, кандидат физико-математических наук Воронов, Василий Юрьевич
Локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации2010 год, доктор физико-математических наук Щербина, Олег Александрович
Введение диссертации (часть автореферата) на тему «Анализ и реализация последовательных и параллельных алгоритмов решения СЛАУ на подпространствах Крылова»
Решение систем линейных алгебраических уравнений (СЛАУ) является одним из основных этапов численного решения задач математической физики; наряду с точностью дискретизации задачи точность решения СЛАУ является важнейшим фактором, влияющим на качество найденного решения [13], [10], [25], [26].
Наряду с задачами математической физики, к необходимости решения СЛАУ приводят и многие другие задачи, например, проблемы распознавания образов, проблемы финансовой и страховой математики и т.д. [40], [42], [59]. Различные подходы к их решению могут приводить к формированию плохо обусловленных и вырожденных систем, включая недоопреде-ленные, решение которых обычно ищется в смысле наименьшей нормы и переопределенные (в случае несовместности последних как правило требуется поиск решения в смысле наименьших квадратов) [1], [57].
Развитие вычислительной техники сделало необходимым создание программных комплексов для данного обязательного этапа численного решения задач. Начиная с 1960-х годов, появилось большое количество программ и программных пакетов для решения СЛАУ, некоторые из которых используются и в настоящее время [34], [35], [44], [52]. Часть таких программных средств является коммерческими продуктами [51], часть объявлена свободно распространяемыми; распространению последних в значительной степени способствуют возможности международной компьютерной сети Internet [22], [25].
Исторически развитие вычислительной техники оказывало значительное влияние на развитие численных методов, используемых для решения реальных задач. Небольшие объемы оперативной памяти первых компьютеров и их низкоскоростные устройства внешней памяти позволяли решать задачи лишь теми методами, которые приводили к СЛАУ с плотными матрицами небольшой размерности либо с разреженными матрицами регулярной структуры, допускающей экономичные способы хранения [13], [20], [10]. Подавляющее большинство программного обеспечения, ведущего свою историю с 1960-х годов, ориентировано на работу именно с такими данными [25]; средства, позволяющие работать с более сложными данными 6 и реализующие более сложные методы, весьма немногочисленны и в большинстве своем носят коммерческий характер.
Быстрое улучшение технических характеристик компьютеров привело к возможности работать с данными гораздо большего объема [40], что в свою очередь, привело к росту популярности методов дискретизации, оперирующих более сложными понятиями. Наряду с методами конечных разностей, получили распространение методы конечных элементов и контрольных объемов [13], [26], [33], [45], [48]; кроме того, все эти методы стали применяться для поиска решений на неструктурированных сетках с локальными сгущениями узлов [26]. Применительно к строящимся в данных методах СЛАУ это означало отказ от регулярной структуры матриц, переход к специальным методам их хранения [32] и итерационным методам решения, не требующим пересчета матрицы (в частности, методам проектирования на подпространствах Крылова [45], [57]).
Однако в силу закрытости и коммерческого характера решаемых такими методами задач, разработанное отдельными коллективами исследователей программное обеспечение не стало общедоступным и в основной массе также осталось закрытым. Стоимость отдельных современных коммерческих пакетов линейной алгебры доходит до сотен тысяч долларов.
Появление отдельных монографий по вычислительным методам для работы с разреженными матрицами [17] не могло изменить ситуацию вплоть до появления многопроцессорных вычислительных комплексов [40]. Резкий роет вычислительных возможностей в сочетании с отсутствием программных средств привел к появлению большого количества работ, посвященных разработке параллельных алгоритмов линейной алгебры, а также адаптации уже существующего программного обеспечения [16], [28], [34], [48], [49], [54], [55].
В 1990-ые годы начали появляться средства, ориентированные на использование современных методов, и реализующие современные алгоритмы. Их количество и качество имеют устойчивую тенденцию к росту, однако распространение подобного программного обеспечения несколько сдерживается отсутствием устоявшихся стандартов на реализацию некоторых деталей, характерных для параллельного программирования (например, синхронизацию и обмен сообщениями) [25]. Кроме того, задачи адаптации существующего и разработки нового программного обеспечения 7 поставили перед разработчиками ряд проблем, многие из которых до настоящего времени не решены [49].
Целью данной работы является исследование ряда методов решения СЛАУ с плотными (включая прямоугольные) и разреженными матрицами, их реализация в виде программного инструмента, удобного для применения в методах конечных элементов и контрольных объемов; объектом исследования в частности является возможность параллельной реализации и изучение ее эффективности.
Научная новизна работы заключается в исследовании малоизученного класса методов решения плотных СЛАУ, предложенного А.А.Абрамовым, детальном анализе входящих в него методов и их связи с другими методами и классами (в частности, с некоторыми методами решения разреженных СЛАУ). Для методов решения разреженных СЛАУ исследуется 1Ш-предобуеловливание и проводится анализ сложности соответствующего алгоритма в зависимости от используемого способа хранения разреженных матриц, что позволяет сделать выводы о целесообразности использования тех или иных форматов представления данных. Для созданных параллельных алгоритмов проводится теоретический анализ эффективности, проверенный серией вычислительных экспериментов.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, приложения, списка литературы и содержит 156 страниц, включая 5 таблиц и 14 иллюстраций. Список литературы содержит 61 наименование.
Похожие диссертационные работы по специальности «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», 05.13.16 шифр ВАК
Высокоточные вычисления с динамической длиной операндов в многопроцессорных системах1999 год, кандидат технических наук Морозов, Виталий Александрович
Параллельная распределенная объектно-ориентированная вычислительная среда для конечно-элементного анализа2004 год, кандидат физико-математических наук Рычков, Владимир Николаевич
Методы расчета картины растекания тока по конструкции космического аппарата от электростатических разрядов на основе макромоделирования2012 год, кандидат технических наук Востриков, Александр Владимирович
Методы решения симметричной проблемы собственных значений и проблемы определения сингулярного разложения с оцениваемой точностью2007 год, кандидат физико-математических наук Мацех, Анна Михайловна
Алгоритмы и программное обеспечение для решения систем линейных алгебраических уравнений при анализе электромагнитного излучения проводных структур2007 год, кандидат технических наук Куксенко, Сергей Петрович
Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Баландин, Михаил Юрьевич
Заключение
В работе получены следующие основные результаты:
• На основе сформулированных А.А.Абрамовым теорем разработаны вычислительные схемы, эффективные для решения плотных плохо обусловленных и вырожденных (включая прямоугольные) СЛАУ. В рамках данного класса исследованы и реализованы методы ABR и ABRIORT. Для метода ABRIORT получена оценка точности, достигаемой в конечной арифметике и сформулированы условия, позволяющие повысить точность. Показана связь класса методов А.А.Абрамова с ABS-классом, доказана эквивалентность методов Ху-анга и ABR в точной арифметике.
• Исследованы и реализованы методы решения СЛАУ с разреженными несимметричных матрицами BiCG и GMRES(m), принадлежащие к классу методов на подпространствах Крылова. Для GMRES(m) исследованы экстремальные случаи выбора размерности подпространства Крылова т.
• Для методов BiCG и GMRES реализовано ILU-предобусловливание, позволяющее значительно ускорить процесс решения. Предобуслов-ливание реализовано для нескольких различных форматов хранения разреженных матриц произвольной структуры; получены соответствующие оценки вычислительной сложности алгоритмов, что позволило сформулировать рекомендации для выбора форматов МКО и МКЭ СЛАУ.
• Разработан программный пакет LinPar, предназначенный для использования в качестве внешнего модуля в программах решения задач математической физики. Пакет включает методы ABR, ABRIORT, CG, BiCG, GMRES(m) с возможностью использования в методах CG, BiCG, GMRES(m) ILU-предобусловливания. Реализована работа с большим количеством форматов представления пользовательских данных. Пакет использован при решении реальных физических задач.
• Для методов ABR, ABRIORT, BiCG, GMRES(m) разработаны и реализованы параллельные алгоритмы. Проведены исследования их эф
107 фективности и получены теоретические оценки асимптотического ускорения; проведен ряд вычислительных экспериментов, показавших хорошее согласование результатов с теоретическими оценками.
I0¡5
Список литературы диссертационного исследования кандидат физико-математических наук Баландин, Михаил Юрьевич, 1999 год
1. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем / пер. с англ. — М.: Мир, 1991.
2. Абрамов А.А. Об одном методе решения плохо обусловленных систем линейных алгебраических уравнений // Журнал вычислительной математики и математической физики. — 1991. — Т.31, № 4. — С. 483-492.
3. Абрамов А.А. О свойствах метода Крейга при решении линейных некорректных задач // Журнал вычислительной математики и математической физики. — 1995. — Т.35, № 1. — С. 144-150.
4. Ильин В.П. Методы неполной факторизации для решения алгебраических систем. — М.: Физматлит, 1995.
5. Писсанецки С. Технология разреженных матриц / пер. с англ. — М.: Мир, 1988.
6. Naiarajan R. Finite Element Applications on a Shared-Memory Multiprocessor: Algorithms and Experimental Results, In: Journal of Computational Physics. — Vol. 94 (1991). — P. 352-381.
7. Aspects of Computational Science. — Stiehting Nationale Computer Faciliteiten, The Netherlands, 1995.
8. Kadioglu М., Mudrick S. On the Implementation of the GMRES(m) method to Elliptic Equations in Meteorology, In: Journal of Computational Physics. — Vol. 102 (1992). — P. 348-359.
9. Vuik K., Sevink A., Herman G. A Preconditioned Krylov Subspace Method for the Solution of Least Squares Problems in Inverse Scattering, In: Journal of Computational Physics. — Vol. 123 (1996). — P. 330-340.
10. Ramadhyani S., Patankar S.V. Solution of the Poisson Equation: comparison of the Galerkin and Control-Volume methods, In: International Journal for Numerical methods in Engineering. — Vol. 15 (1980). — P. 1395-1418.
11. Фаддеева В.И., Колотилина Л.Ю. Вычислительные методы линейной алгебры. Набор матриц для тестирования. Л., 1982.
12. Бйлнндии М.Ю., Шурина Э.П. Некоторые оценки эффективности параллельных алгоритмов решения СЛАУ на подпространствах Крылова // Вычислительные технологии. — 1998. — Т.З, № 1. — С. 23-30.
13. Saad ¥., Schuitz М.Н. GMRES: a generalized minimal residual aigo= rithiii for solving non-symmetric linear systems, In: SIAM Journal for Scientific and Statistical Computing. — Vol. 7 (1986). — P. 856-869.1501. Список литературы
14. Абаффи Й., Спедикато Э. Математические методы для линейных и нелинейных уравнений: проекционные ABS-алгоритмы. / пер с англ. — М.: Мир, 1996
15. Абрамов A.A. Об одном методе решения плохо обусловленных систем линейных алгебраических уравнений. / ЖВМиМФ, 1991 — Т. 31, № 4 — С. 483-492
16. Абрамов A.A. О свойствах метода Крейга при решении линейных некорректных задач. / ЖВМиМФ, 1995 — Т. 35, №1 — С. 144-150
17. М.Ю. Баландин, Э.П. Шурина Некоторые оценки эффективности параллельных алгоритмов решения СЛАУ на подпространствах Крылова. / "Вычислительные технологии", 1998 — Т. 3, № 1 — С. 23-30
18. М.Бочев, Л.Крукиер Об итерационном решении сильно несимметричных систем линейных алгебраических уравнений. / Журнал вычислительной математики и математической физики, 1997, т. 37, № 11, с. 1283-1293
19. Воробьев Е.М. Введение в систему «Mathemalica». — М.: Финансы и статистика, 19988} Говорухин В.Н., Цибулин В.Г. Введение в Maple. — М.: Мир, 1997
20. Годунов С.К. Современные аспекты линейной алгебры. — Новосибирск: Научная книга, 1997.151
21. Годунов С.К. Воспоминания о разностных схемах. Доклад на международном симпозиуме «Метод Годунова в газовой динамике», Мичиганский университет, США. — Новосибирск: Научная книга, 1997
22. Дьяконов В.П. MathCAD PLUS 6.0 PRO. Универсальная система математических расчетов. — М.: СК Пресс, 1997
23. Дьяконов В.П. Справочник по системе символьной математики Derive. — М.: СК Пресс, 1998
24. Ильин В.П. Методы неполной факторизации для решения алгебраических систем. — М.: Физматлит, 1995
25. Mathcad. Руководство пользователя Mathcad 6.0, Mathcad 6.0 PLUS. — М.: Филинь, 1997
26. Манзон Б.М. Maple V Power Edition. — М.: Филинь, 1998
27. Дж. Ортега Введение в параллельные и векторные методы решения линейных систем / пер. с англ. — М.: Мир, 1991
28. Писсанецки С. Технология разреженных матриц. / пер. с англ. — М.: Мир, 1988
29. Поляченко Д.В., Резник А.А. Устойчивый метод неполной факторизации для симметричных разреженных матриц. — М.: Инст. Матем. Моде-лир. РАН, 1995, No 16
30. Уилкинсон Дж. Алгебраическая проблема собственных значений
31. Уилкинсон Дж., Райнш К. Справочник алгоритмов на языке АЛГОЛ: Линейная алгебра. — М.: Машиностроение, 1976
32. Фаддеева В.Н., Колотилида Л.Ю. Вычислительные методы линейной алгебры: набор матриц для тестирования. Материалы по программному обеспечению ЭВМ. Л.: 1982.152
33. Г.С.Хакимзянов, Л.Б.Чубаров Программный инструментарий математика: учебное пособие, часть 1. — Новосибирск: НГУ, 1998
34. Г.С.Хакимзянов, Л.Б.Чубаров Аналитические вычисления и визуализация результатов. Программный инструментарий математика: учебное пособие, часть 2. — Новосибирск: НГУ, 1998
35. Aspects of Computational Science. — Stichting Nationale Computer Fa-cilitetiten, The Netherlands, 1995
36. W.Anderson, RRausch, D.Bonhaus Implicit/Multigrid Algorithms for Incompressible Turbulent Flows on Unstructured Meshes. / Journal of Computational Physics, 128, 391-408 (1996)
37. A.Abramov The Properties Craig Procedure for Solving Linear Ill-posed Problems. / Сотр. Maths Math. Phys., Vol. 35, No 1, pp. 113-117 (1995)
38. L.Auslander, A.Tsao On Parallelizable Eigensolvers / Advances in Applied Mathematics, 13, 253-261 (1992)
39. Balandin M.Yu. et al. On Parallelization of New Algorithm for Solving Systems of Linear Equations, In: Joint Bulletin of the Novosibirsk Computer Center and the Institute of Informatics Systems. — Series "Computer Science", issue 4(96). — P. 17-26
40. R.Choquet, P.Leyland, T.Tefy GMRES Acceleration of Iterative Implicit Finite Element Solvers for Compressible Euler and Navier-Stokes Equations / International Journal for Numerical Methods in Fluids, vol.20, 957-967, (1995)
41. E.Chow, Y.Saad ILUS: an Incomplete LU Preconditioner in Sparse Skyline Format / International Journal for Numerical Methods in Fluids, vol.25, 739-748 (1997)
42. A.Degani, G.Fox Parallel Multigrid Computation of the Unsteady Incompressible Navier-Stokes Equations / Journal of Computational Physics, 128, 223236 (1996)
43. J.Dongarra Performance of Various Computers Using Standard Linear Equations Software in a Fortran Environment, Computer Science Technical Report, Univ. of Tennessee, 1990
44. J.Dongarra et al. An Extended Set of Fortran Basic Linear Algebra Subprograms, ACM Trans. Math. Softw., 14 (1988), 1-17
45. J.Dongarra et al. A set of Level 3 BLAS, ACM Trans. Math. Softw., 16 (1990), 1-17
46. J.Dongarra et al. Solving Linear Systems on Vector and Shared Memory Computers. — SI AM, Philadelphia, 1991
47. V.Fraysse, L.Giraud, S.Gratton A Set of GMRES Routines for Real and Complex Arithmetics / CERFACS Technical Report TR'PA/97/49
48. G.Gottlieb, P.Fischer Modified Conjugated Gradient Method for the Solution of Ax=b. / Journal of Scientific Computing, Vol. 13, No 2, 1998
49. M. Heath, G. Geist, J. Drake Early Experience With the Intel iPSC/860 at Oak Ridge National Laboratory / The International Journal of Supercomputer Applications, Vol.5, No 2 (1991), 10=26
50. R.Janardhan, T.Downar A Nested FGMRES Method for Parallel Calculation of Nuclear Reactor Transients. / Journal of Scientific Computing, Vol. 13, No 1, 1998154
51. M.Kadioglu, S.Mudrick On the Implementation of the GMR£S(m) method to Elliptic Equations in Meteorology / Journal of Computational Physics, 102, 348-359 (1992)
52. M.Kooper et al. Application of the Implicitly Updated Arnoldi Method with a Complex Shift-and-Itivert Strategy in MHD. / Journal of Computational Physics, 118, 320-328 (1995)
53. C.Lawson et al. Basic Linear Algebra Subprograms for Fortran Usage. / ACM Trans. Math. Softw., 5 (1979), 305=329
54. A.Meister Comparison of Different Krylov Subspace Methods Embedded in an Implicit Finite Volume Scheme for the Computation of Viscous and Inviscid Flow Fields on Unstructured Meshes / Journal of Computational Physics, 140, 311-345(1998)
55. I.Moret A Note on the Superlinear Convergence of GMRES, / SIAM J. Numer. Ana!., Vol. 34, No. 2 (1997), 513-516
56. S.Mulyarchik, S.Bielawski, A.Popov Efficient Computational Schemes of the Conjugate Gradient Method for Solving Linear Systems / Journal of Compu^ tational Physics, 110,201-211 (1994)
57. R.Natarajan Finite Element Applications on a Shared-Memory Multiprocess sor: Algorithms and Experimental Results / Journal of Computational Physics, 94, 352=381 (1991)
58. T.Rauber, G.Runger Optimal Data Distribution for LU Decomposition / EURO-PAR'95 Parallel Processing, 1st International conference proceedings, — Springer-Verlag, "Lecture Notes in Computer Science" series. — Vol. 966. — P. 391-402
59. Y. Saad, H. Schultz GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, / SIAM J. Sei. Stat. Comput, 7, 856-869 (1986)155
60. S. Salvini, G.Shaw An evaluation of new NAG library solvers for large sparse symmetric linear systems, NAG technical report TRI/95, NP2870.
61. B.Smith et al. Matrix Eigensystem Routes: EISPACK Guide. — Berlin, Springer=Verlag, 1976
62. B.Tanyi, R.Thatcher Iterative Solution of the Incompressible Navier-Stokes Equations on the Meiko Computing Surface / International Journal for Numerical Methods in Fluids, vol.22, 225-240, (1996)
63. V.Taylor, A.Ranade, D.Messershmitt SPAR: A New Architecture for Large Finite Element Computations / IEEE Transactions on Computers, vol.44, No.4, 1995 (531=544)
64. C.Vuik Fast Iterative Solvers for the Discretized Incompressible Navier-Stokes Equations. / international Journal for Numerical Methods in Fluids, vol.22, 195=210, (1996)
65. K.Vuik, A.Sevink, G.Herman A Preconditioned Krylov Subspace Method for the Solution of Least Squares Problems in Inverse Scattering. / Journal of Computational Physics, 123, 330-340 (1996)
66. D.Young, R.Melvin, M.Bieterman, F.Johnson, S.Samant, J.Bussoletti A Locally Refined Rectangular Grid Finite Elemet Method: Application to Computational Fluid Dynamics and Computational Physics / Journal of Computational Physics, 92, 1=66 (1991)
67. Y.Zhao, K. Anastasiou Modeling of Wave Propagation in the Nearshore Region Using the Mild Slope Equation with GMRES-based Iterative Solvers, In: International Journal for Numerical Methods in Fluids, Vol. 23, 397-411 (1996)156
68. Ramadhyani S., Patankar S.V. Solution of the Poisson Equation: comparison of the Galerkin and Control-Volume methods / International Journal for Numerical methods in Engineering. — Vol. 15 (1980). — P. 1395-1418.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.