автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Анализ и реализация последовательных и параллельных алгоритмов решения СЛАУ на подпространствах Крылова

Введение

Глава 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 Пример использования в физическом приложении

Решение систем линейных алгебраических уравнений (СЛАУ) является одним из основных этапов численного решения задач математической физики; наряду с точностью дискретизации задачи точность решения СЛАУ является важнейшим фактором, влияющим на качество найденного решения [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 наименование.

Заключение

В работе получены следующие основные результаты:

• На основе сформулированных А.А.Абрамовым теорем разработаны вычислительные схемы, эффективные для решения плотных плохо обусловленных и вырожденных (включая прямоугольные) СЛАУ. В рамках данного класса исследованы и реализованы методы 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

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.