Параллельные методы решения систем линейных уравнений с симметричными положительно-определенными матрицами на основе аддитивного разложения с перекрытиями тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Коньшин, Игорь Николаевич

• Коньшин, Игорь Николаевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Коньшин, Игорь Николаевич

Введение

1 Метод сопряженных градиентов (МСГ)

1.1 Прямые и итерационные методы решения линейных систем

1.2 Описание предобусловленного метода сопряженных градиентов

1.3 Оценка сходимости МСГ через спектральное число обусловленности

1.4 Оценка сходимости МСГ через К-число обусловленности

1.5 Устойчивость предобусловливаний МСГ.

2 Методы приближенных треугольных разложений

2.1 Предобусловливания, основанные на треугольном разложении.

2.2 Неполные и приближенные треугольные разложения

2.3 Предварительное масштабирование как этап предобусловливания.

2.4 Теория приближенного треугольного разложения

2-го порядка.

2.4.1 Приближенное треугольное разложение 2-го порядка

2.4.2 Улучшение обусловленности, достигаемое применением приближенных треугольных разложений.

2.4.3 Устойчивость приближенных треугольных разложений

2.5 Алгоритмы безотказного приближенного треугольного разложения.

2.6 Трудности распараллеливания IC2 разложения.

3 Параллелизуемое аддитивное предобусловливание

3.1 Методы построения параллельных предобусловливаний

3.1.1 Использование окаймленной блочно-диагональной структуры.

3.1.2 Использование приближенных обратных матриц

3.2 Блочное неполное обратное треугольное разложение.

3.2.1 Построение BIIC-предобусловливания.

3.2.2 Оценка качества предобусловливания по методу BIIC-IC2.

3.3 Диагональное и блочно-диагональное предобусловливание

4 Параллельная реализация и балансировка вычислений

4.1 Параллельные ЭВМ и параллельные вычисления

4.2 Параллельная реализация итерационных методов.

4.3 Описание параллельной реализации.

4.4 Способы балансировки вычислений

4.5 Теоретический анализ стратегий постфильтрации построенного предобусловливателя.

4.6 Описание реализации балансировки и применения параллельного ВПС-1С2-предобусловливания.

5 Численные эксперименты

5.1 Тестовые задачи и методика проведения численных экспериментов

5.2 Численные эксперименты для задач упругости тонкостенных оболочек.

5.3 Численные эксперименты для задач теории линейной упругости в механике упругого тела.

5.4 Численные эксперименты по балансировке вычислений для задач из коллекции университета Флориды.

5.5 Сравнение метода ВНС-1С2-МСГ с другими методами

Введение диссертации (часть автореферата) на тему «Параллельные методы решения систем линейных уравнений с симметричными положительно-определенными матрицами на основе аддитивного разложения с перекрытиями»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Объект исследования и актуальность темы. Актуальность темы диссертационной работы обусловлена необходимостью эффективного численного решения систем линейных алгебраических уравнений с разреженными симметричными положительно-определенными матрицами большой размерности. Численное решение систем линейных уравнений является одной из наиболее часто встречающихся задач в научно-технических исследованиях и практических приложениях. Подобные задачи возникают, например, в математической физике при численном решении дифференциальных и интегральных уравнений. При этом прикладные задачи часто требуют решения систем линейных уравнений с большим числом неизвестных. К таким системам, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов. Для возникающих систем линейных уравнений применение прямых методов решения оказывается неприемлемым как по причине большого времени решения, так и недостаточности объема оперативной памяти для хранения данных задачи. Итерационные методы решения систем линейных уравнений намного экономичнее с точки зрения использования оперативной памяти, но для ускорения их сходимости требуется строить эффективные предобусловливания, особенно при решении систем с плохо обусловленными матрицами.

Существенные затруднения связаны с тем, что наиболее актуальной задачей является решение систем линейных уравнений настолько большой размерности, что их решение возможно только на современных параллельных ЭВМ с распределенной памятью, что подразумевает разбиение данных на блоки, каждый из которых обрабатывается отдельным процессором. Поэтому для таких многопроцессорных вычислительных машин необходимо построение специальных параллельных предобусловливаний, использующих разбиение на блоки матрицы решаемой системы. Причем для универсальности метода требуется построение разбиения на блоки без привлечения информации о пространственном расположении узлов расчетной сетки.

Эффективность использования каждого процессора многопроцессорной ЭВМ в конечном итоге определяет эффективность решения задачи в целом, поэтому регулирование загруженности процессоров также является актуальной задачей. Использование специальных методов балансировки вычислений на различных процессорах призвано решить задачу повышения эффективности параллельных вычислений.

Целью диссертационной работы является разработка, исследование и реализация на параллельных ЭВМ высокопроизводительного итерационного метода решения жестких систем линейных алгебраических уравнений с разреженными симметричными положительно-определенными матрицами, а также численные исследования работоспособности предложенного метода для различных типов плохо обусловленных систем линейных уравнений.

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

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

2. Разработка эффективного способа балансировки вычислений для подзадач на различных процессорах.

3. Исследование эффективности метода в зависимости от параметров предобусловливания и количества процессоров.

4. Подтверждение эффективности метода для различных типов решаемых задач и на различных вычислительных системах.

Методы исследования. В диссертационной работе используется математический аппарат численных методов, теории итерационных алгоритмов, линейной алгебры, теории графов, методов параллельного программирования.

Научная новизна:

1. Установлено, что при однопроцессорной реализации методов решения систем линейных уравнений с симметричными положительно-определенными матрицами, метод приближенного треугольного разложения второго порядка существенно превосходит по качеству пре-добусловливания аналогичные методы первого порядка.

2. Показано, что предложенная схема построения параллельного предо-бусловливания имеет более высокую скорость сходимости по сравнению с некоторыми известными схемами типа декомпозиции области.

3. Предложена комбинация приближенного треугольного разложения второго порядка и неполного обратного треугольного разложения, позволяющая получить высокое качество параллельного предобуслов-ливания.

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

5. Проведены численные эксперименты, показавшие, что как общие арифметические затраты, так и количество итераций для предложенного метода слабо зависят от количества используемых процессоров по сравнению с известными параллельными предобусловливаниями.

6. Численными экспериментами подтверждена теоретически обоснованная высокая параллельная эффективность и вычислительная надежность разработанного метода.

Научная и практическая ценность. Разработан параллельный метод решения жестких систем линейных алгебраических уравнений с симметричными положительно-определенными матрицами, который может быть использован во многих приложениях. Предложенный метод показал высокую надежность и эффективность при решении задач из самых различных научных и практических областей применения. Выполненная работа вносит теоретический и практический вклад в развитие высокопроизводительных параллельных вычислений, так как она призвана не только решить проблему экономии памяти и сокращения времени вычислений при решении систем линейных уравнений, но и сделать возможным решение задач, которые ранее в принципе не могли быть решены на однопроцессорных компьютерах.

Положения, выносимые на защиту:

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

2. Методика балансировки вычислений на основе восполнения треугольных сомножителей элементами матрицы ошибок.

3. Результаты практического исследования эффективности предложенного алгоритма на тестовых и прикладных задачах, его вычислительных и коммуникационных затрат, а также времени счета при изменении параметров предобусловливания и количества процессоров.

Обоснованность и достоверность результатов основывается на строгих математических доказательствах и проверке теории в численных экспериментах. Эффективность построения параллельного предобусловливания обосновывается использованием широкого ряда тестовых задач для верификации полученных численных результатов, а также прямым сравнением результатов расчетов с результатами, полученными при использовании других предобусловливаний семейства блочных методов Якоби. Достоверность того, что предложенный метод является эффективным, подтверждена результатами расчетов и сравнением с результатами других авторов на примере задач из коллекции университета Флориды.

Апробация работы. Результаты работы докладывались и обсуждались на международной конференции "РаСТ99" (Санкт-Петербург, Россия, 1999 г.), Всемирном 16-ом Конгрессе "IMACS 2000" по научным вычислениям, прикладной математике и моделированию (Лозанна, Швейцария, 2000), Голландско-российском симпозиуме NWO (МГУ, Москва, июнь 2000), Симпозиуме NWO (Амстердам-Ниймеген, Голландия, ноябрь 2000), Втором Международном научно-практическом Семинаре и Всероссийской молодежной школе "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, Россия, 2002), Международной конференции "Parallel CFD 2003" (Москва, 2003), Международной конференции "VIII Забабахинские научные чтения" (РФЯЦ-ВНИИТФ, Сне-жинск, Россия, 2005), Международной конференции по численной геометрии, построении расчетных сеток и научным вычислениям "NUM-GRID2008" (ВЦ РАН, Москва, 2008), на научно-исследовательских семинарах Вычислительного центра РАН, Московского физико-технического института, Института автоматизации проектирования РАН, а также на семинарах Департамента информационных технологий Республики Индия (С-DAC, Пуна, Индия), Institut Frangais du Petrol (Париж, Франция), ExxonMobil Upstream Research Co. (Хьюстон, США).

Личный вклад соискателя. В работах соискателя соавтором является научный руководитель Капорин И. Е., ему принадлежит постановка задач и выбор математических методов исследований. Соискателем проведены теоретические исследования, разработаны параллельные предобусловливания, выполнены параллельные реализации предложенных алгоритмов и исследованы границы применения предложенных методов.

Публикации. Основные публикации по теме диссертации включают 11 работ, из них 3 работы [27, 28, 37] в ведущих отечественных и международных рецензированных научных изданиях, рекомендованных ВАК, 3 в других международных рецензируемых изданиях, 1 в российском рецензируемом издании, 1 в трудах международной конференции, 3 публикации в других научных изданиях.

Кроме того, по теме диссертации имеются публикации в трудах и тезисах 7 всероссийских и 16 международных конференций.

Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы, содержит 18 таблиц и 23 рисунка. Объем работы 138 страниц. Список литературы включает в себя 112 наименований.

Заключение диссертации по теме «Вычислительная математика», Коньшин, Игорь Николаевич

Основные результаты

1. Разработан, исследован и реализован новый параллельный метод ВНС-1С2-МСГ решения жестких линейных систем с разреженными с.п.о. матрицами.

2. Разработана, исследована и реализована новая методика балансировки вычислений для подзадач на различных процессорах.

3. В численных экспериментах показана надежность предложенного метода, в частности, относительно изменения таких параметров предобусловливания, как параметр отсечения малых элементов, параметр перекрытия и количество блоков.

4. Показана высокая параллельная эффективность предложенного метода, вплоть до сверхлинейного ускорения.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Коньшин, Игорь Николаевич, 2009 год

1. Коиъшин И.Н. Особенности решения линейных систем на вычислительных системах с матричными процессорами // 5-я Московская конференция по проблемам кибернетики и вычислений. Научный совет "Кибернетика" АН СССР, Статистический отдел "Москва". Москва. 1986.

2. Коньшин И.Н. Блочные методы исключения на параллельных ЭВМ для ленточных СЛАУ большой размерности // Организация вычислений на супер-ЭВМ. МФТИ. Москва. 1987. Деп. ВИНИТИ N.2184-B87, 7с.

3. Коньшин И.Н., Малясов С.А. О применении метода разбиения области в одной задаче квантовой механики // Сопряженные уравнения и алгоритмы возмущения. ОВМ АН СССР. Москва. 1988. С.92-98.

4. Коньшин И.Н. О реализации методов разбиения области на вычислительных системах с матричными процессорами j j Методы математической физики. ОВМ АН СССР. Москва. 1988. 23с.

5. Коньшин И.Н., Еремин А.Ю. Проблемы отображения многоуровневых алгоритмов разбиения области на архитектуру параллельных ЭВМ // 2-й Семинар соц. стран "Вычислительная механика и автоматизация проектирования". Москва-Ташкент. 1988.

6. Коньшин И.Н. Оптимизация многосеточных методов декомпозиции области // Численные методы и программное обеспечение. ОВМ АН СССР. Москва. 1990. 22с.

7. Gushchin V.A., Kononov I.N., Konshin I.N., Konshin V.N. Parallel numerical modeling of clean room air flows // The third Russian-Japan joint symposium on CFD. Book of abstracts. Part II. August 25-30, 1992. Vladivostok. Russia. P.121-122.

8. Кононов И.Н., Коньшин B.H., Коньшин И.Н. Численный анализ потоков воздуха в чистом производственном помещении // Сб. докл. 2-й конференции ассоциации инженеров по контролю микро-загрязнений. 12-16 октября, 1992. АСИНКОМ-92. Суздаль. 1992. С.136-140.

9. Kaporin I.E., Konshin I.N. Parallel solution of SPD linear systems based on algebraic DD // In: Proc. of European Conference on Parallel Computing, Euro-Par 2000. 29.8.-1.9.2000, Munich, Germany. 2000. 6p.

10. Kaporin I., Konshin I. Accuracy and efficiency of parallel implementation of matrix multiplication. // In: Proc. of 6th International IMACS Conference on Applications of Computer Algebra. St. Petersburg, Russia. June 25-28, 2000. P.ll.

11. Konshin I.E., Kaporin I.E. Parallel solution of STW linear systems based on BIIC2 preconditioning // Dutch-Russian NWO Workshop. Moscow State University, Moscow. June 23-24, 2000.

12. Konshin I., Kaporin I. Numerical testing of parallel solvers for a set of benchmark problems // NWO Workshop 2000. 16-17 November 2000, CWI, Amsterdam. 21 November 2000, KUN, Nijmegen.

13. Kaporin I.E., Konshin IN. Benchmark problems in linear elasticity: parallel solution // Tech. Report No.0028. Department of Mathematics, University of Nijmegen, The Netherlands, December 2000. 22p.

14. Капорин И.Е., Коньшин И.Н.: Параллельное решение симметричных положительно-определенных систем на основе перекрывающегося разбиения на блоки // Ж. Вычисл. Матем. и Матем. Физ. 2001. Т.41, N.4, Р.515-528.

15. Kaporin I.E., Konshin I.N. A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems //J. Numer. Lin. Alg. Appl. 2002. Vol.9. No.2. P.141-162.

16. Garanzha V.A., Kaporin I.E., Konshin I.N. Truncated Newton type solver with application to grid untangling problem //J. Numer. Lin. Alg. Appl. 2004. Vol.11. No.5-6. P.525-533.

17. Kaporin I.E., Konshin I.N. Recursive scaling, permutation and 2x2-block splitting in ILU preconditionings // In: Proc. 2-nd International Conference on Matrix Methods and Operator Equations. July 23-27, 2007. Moscow. P.33-34.

18. Капорин И.Е., Коньшин И.Н. Постфильтрация множителей IC2-разложения для балансировки параллельного предобусловливания // Ж. Вычисл. Матем. и Матем. Физ. 2009. Т.49. N.6. С.940-957.

19. Вогачев К.Ю. Основы параллельного программирования М.: Бином. 2003.

20. Еремин А.Ю., Капорин И.Е. Частичное исключение как способ переобусловливания // Препр. №216. М.: Отд. Вычисл. Матем. АН СССР. 1988. 11 с.

21. Капорин И.Е. О предобусловливании и распараллеливании метода сопряженных градиентов //В (Ортега Дж.) Введение в параллельныеи векторные методы решения линейных систем. М.: Мир. 1990. С.343-355.

22. Капорин И.Е. О предобусловливании метода сопряженных градиентов при решении дискретных аналогов дифференциальных задач // Дифферент ур-ния. 1990. Т.26. N.7. С.1225-1236.

23. Капорин И.Е. Двухуровневые явные предобусловливания метода сопряженных градиентов // Дифференц. ур-ния. 1992. Т.28. N.2. С.329-339.

24. I. Е. Kaporin. Explicitly preconditioned conjugate gradient method for the solution of nonsymmetric linear systems // Int. J. Computer Math. 1992. Vol.40. P.169-187.

25. Капорин И.Е. Оценки границ спектра двусторонних явных предобус-ловливаний // Вестн. МГУ. Выц.15. Вычисл. матем. и кибернетика 1993. Т.2. С.28-42.

26. Милюкова О.Ю. Некоторые параллельные итерационные методы с факторизованными матрицами предобусловливания для решения эллиптических уравнений на треугольных сетках // Ж. Вычисл. Матем. и Матем. Физ. 2006. Т.46. N.6. С.1096-1113.

27. Ортега Дою. // Введение в параллельные и векторные методы решения линейных систем. М.: Мир. 1990.

28. Посыпкин М.А., Хританков А.С. О понятии производительности в распределенных вычислительных системах // Проблемы вычислений в распределенной среде. М.: Труды Института Системного Анализа РАН. 2008. Т.32. С.26-32.

29. Хейгеман Л., Янг Д. // Итерационные методы. М.: Мир. 1990.

30. Ajiz М.А., Jennings A. A robust incomplete Choleski-conjugate gradient algorithm // Int. J. Numer. Methods Engrg. 1984. Vol.20. P.949-966.

31. Axelsson 0. A class of iterative methods for finite element equations // Computer Meth. Appl. Mech. Engrg. 1976. Vol.9. No. 2. P.123-137.

32. Axelsson 0., Lindskog G. On the rate of convergence of the preconditioned gradient methods // Numer. Math. 1986. Vol.48. No. 5. P.499-523.

33. Axelsson 0. // Iterative Solution Methods. Cambridge University Press, Cambridge, New York. 1994.

34. Axelsson O., Kaporin I., Kucherov A., Neytcheva M. Benchmark problems in linear elasticity. Part I: Direct and robust second order incomplete factorization methods, (submitted to Int. J. Numer. Methods Engrg.)

35. Benzi M., Kouhia R., Тита M. An assessment of some preconditioning techniques in shell problems // Techn. Rept LA-UR-97-3892. Los Alamos Nat. Lab., Los Alamos, NM. 1997.

36. Benzi M. Preconditioning Techniques for Large Linear Systems: A Survey. // Journal of Computational Physics. 2002. Vol.182. No.2. P.418-477.

37. Benzi M., Тита T. A robust incomplete factorization preconditioner for positive definite matrices // Numer. Linear Algebra Appl. 2003. V.10. P.385-400.

38. Campos F.F., Birkett N.R.C. An efficient solver for multi-right-hand-side linear systems based on the CCCG(?7) method with applications to implicit time-dependent partial differential equations // SIAM J. Sci. Com-put. 1998. Vol.19. P.126-138.

39. Chow E., Saad Y. Approximate inverse preconditioners via sparse-sparse iterations. // SIAM Journal on Scientific Computing. 1998. Vol.19. No. 3. P. 995-1023.

40. Chow E. A priori sparsity patterns for parallel sparse approximate inverse preconditioners // SIAM J. on Scientific Computing. 2000. Vol.21. No.5. P. 1804-1822

41. Chow E. Parallel implementation and practical use of sparse approximate inverse preconditioners with a priori sparsity patterns // Int. Journal of High Performance Computing Applications. 2001. Vol.15. No.l. P.56-74.

42. Concus P., Golub GO'Leary D. Generalized conjugate gradient method for the numerical solution of elliptic partial differential equations // In: Sparse matrix computations. (Eds. J.Bunch, D.Rose) 1976. P.309-332.

43. Cuthill E., McKee J. Reducing the bandwidth of sparse symmetric matrices. // In: Proceedings of the 24th National Conference of the ACM. 1969. P.152-172.

44. Davis T.A. // University of Florida Sparse Matrix Collection. 2009 http: / / www.cise.ufi.edu/research / sparse / matrices

45. Dennis J.E., Wolkowicz H. Sizing and least change secant methods // SIAM J. Numer. Anal. 1993. Vol.10. P.1291-1314.

46. Dubrulle A. A. Retooling the method of block conjugate gradients // Electr. Transact. Numer. Anal. 2001. Vol.12. P.216-233.

47. Duff I.S., Reid J.K. Performance evaluation of codes for sparse matrix problems //In: Performance Evaluation of Numerical Software (Ed. L.D.Fosdick). Elsevier, North-Holland, New York. 1979. P.121-135.

48. Duff I.S., Grimes R.G., Lewis J.G. Sparse matrix test problems // ACM Trans. Math. Softw. 1989. Vol.15. No.l. P.l-14.

49. Duff I.S., Grimes R.G., Lewis J.G. The Rutherford-Boeing sparse matrix collection // Tech. Report TR/PA/97/36. CERFACS, Toulouse, France.

50. Tech. Report RAL-TR-97-031. Rutherford Appleton Lab. Tech. Report ISSTECH-97-017. Boeing Information and Support Service. 1997.

51. Duff I.S., Riyavong S., Van Gijzen B. Parallel preconditioners based on partitioning sparse matrices // Report RAL-TR-2004-040. Сотр. Sci. and Engrg. Dept., Atlas Centre, Rutherford Appleton Lab., Oxon, 2004. 19p.

52. Eisenstat S.C., Gursky M.C., Schultz M.H., Sherman A.H. Yale sparse matrix package I: The symmetric codes // Int. J. Numer. Methods Engrg. 1982. Vol.18. P.1145-1151.

53. Feng Y.Y., Owen D.R.J., Peric D. A block conjugate gradient method applied to linear systems with multiple right-hand sides // Comput. Meth. Appl. Mech. Engrg. 1995. Vol.127. P.203-215.

54. Graham, E., Forsyth P.A. Preconditioning methods for very ill-conditioned three-dimensional linear elasticity problems // Int. J. Numer. Meths. Engrg. 1999. Vol. 44. P.77-99.

55. Hestenes M.R., Stiefel E. Methods of conjugate gradients for solving linear systems // J. Research Nat. Bur. Standards. 1952. Vol.49. P.409-436.

56. Hypre, High Performance Preconditioners: Users Manual. // Technical Report. Lawrence Livermore National Laboratory. 2006.

57. Jennings A., Malik G.M. Partial elimination // J. Inst. Math. Appl. 1977. Vol.20. P.307-316.

58. Jimack P.K. Domain decomposition preconditioning for parallel PDE software // Engineering computational technology. Civil-Comp press. Edinburgh. UK. 2002.

59. Jones M. Т., Plassman P.E. An improved incomplete Cholesky factorization // ACM Trans. Math. Software. 1995. Vol.21. P.5-17.

60. И.Е. Капорин. О предобусловливаиии метода сопряженных градиентов при решении дискретных аналогов дифференциальных задач // Дифферент ур-ния 1990. Vol.26. No. 7. Р.1225-1236.

61. Kaporin I. Explicitly preconditioned conjugate gradient method for the solution of unsymmetric linear systems // Internat. J. Comput. Math. 1992. Vol.40. P.169-187.

62. Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method // Numer. Linear Algebra and Appl. 1994. Vol.1. No.,2. P.179-210.

63. Kaporin I.E. High quality preconditioning of a general symmetric positive definite matrix based on its UTU + UTR + RT/-decomposition. // Numer. Linear Algebra and Appl. 1998. Vol.5. No.5. P.483-509.

64. Kaporin I.E. Optimizing the UTU + UTR + Дг /-decomposition based Conjugate Gradient preconditionings // Rep. 0030. November 2000. Department of Mathematics, Catholic University of Nijmegen, Nijmegen, The Netherlands. 16p.

65. Karypis G., Kumar V. Multilevel k-way hypergraph partitioning // Tech. Report 98-036. Dept. Сотр. Sci. Engrg., Army HPC Research Center, Univ. of Minnesota, MN. 1998.

66. Kershaw D.S. The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations //J. Comput. Physics. 1978. Vol.26. P.43-65.

67. Kolotilina L.Yu., Yeremin A.Yu. Factorized sparse approximate inverse preconditionings, I: theory // SIAM Journal on Matrix Analysis and Applications. 1993. Vol.14. No.l. P.45-58.

68. Lipton R.J., Rose D.J., Tarjan R.E. Generalized nested dissection // SIAM J. Numer. Anal. 1979. Vol.16. P.346-358.

69. Maclahlan S., Saad Y. A greedy strategy for coarse-grid selection // SIAM J. Sci. Comput. 2007. V. 29. No. 5. P. 1825-1853.

70. Manteuffel T.A. An incomplete factorization technique for positive definite linear systems // Math. Comput. 1980. Vol.34. P.473-497.

71. Marshall A.W., Olkin I. /j Inequalities: Theory of Majorization and its Applications. Academic Press, New York. 1979.

72. MatrixMarket collection of sparse matrices. 2009 http://math.nist.gov/MatrixMarket.

73. Message Passing Interface (МР1'). http://www.mpi-forum.org/docs/docs.html

74. MPICH. http://info.msc.anl.gov/pub/mpi

75. Notay Y. On the convergence rate of the conjugate gradients in presence of rounding errors // Numer. Math. 1993. Vol.65. P.301-317.

76. O'Leary D.P. The block conjugate gradient algorithm and related methods // Linear Algebra and Appls. 1980. Vol.29. P.293-322.99. http://www.parallel.ru

77. Rao V.N., Kumar V. Parallel depth-first search, part II: Analysis j I Int. J. Par all. Programming. 1987. Vol.16, No.6. P.501-519.

78. Ruge J. W., Stiiben K. Algebraic multigrid (AMG) // Multigrid Methods (Ed. McCormick S. F.) Frontiers Appl. Math. Vol. 3. Philadelphia: SIAM. 1987. P. 73-130.

79. Saad Y. // Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics. Philadelphia. PA. 2003.

80. Saad Y., Suchomel B. ARMS: An algebraic recursive multilevel solver for general sparse linear systems // Numer. Linear Algebra Appl. 2002. Vol.9. P.359-378.

81. Suarjana M., Law K.H. A robust incomplete factorization based on value and space constraints // Int. J. Numer. Methods Engrg. 1995. Vol.38, P.1703-1719.

82. The TOP500 Supercomputer Sites. http://www.top500.org, 2009.

83. Tismenetsky M. A new preconditioning technique for solving large sparse linear systems // Linear Algebra and Appl. 1991. Vol.154-156. P.331-353.

84. Tuff A. D., Jennings A. An iterative method for large systems of linear structural equations // Int. J. Numer. Methods Engrg. 1973. Vol.7. P.175-183.

85. Ugar В., Aykanat C. Partitioning sparse matrices for parallel preconditioned iterative methods // SIAM J. Sci. Comput. 2007. Vol.29. No.4. P.1683-1709.

86. Ugar В., Aykanat C. Revisiting hypergraph models for sparse matrix partitioning // SIAM Review. 2007. Vol.49. No.4. P.595-603.

87. Vastenhouw В., Bisseling R.H. A two-dimensional data distribution method for parallel sparse matrix-vector multiplication // SIAM Review. 2005. Vol.47. No.l. P.67-95.

88. Wilkinson J.H., Reinsch C. // Handbook for automatic computation. Linear algebra, Part II. Springer-Verlag, Berlin. 1971.