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

• Падий, Александр Викторович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Падий, Александр Викторович

Оглавление

Введение

1 Алгебраические методы многоуровневых итераций (АММИ)

1.1 Двухуровневый метод. Усиленное неравенство Коши-Буняковского

1.2 Многоуровневый метод. Стабилизация числа обусловленности

2 Аддитивная версия АММИ для анизотропной задачи диффузии

2.1 Постановка задачи

2.2 Аддитивная версия АММИ с внутренними итерациями

2.3 Обобщенный метод сопряженных градиентов

2.4 Алгоритм построения аппроксимаций к блокам A\i

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

3 Модельный анализ проекционного переобуславливателя

3.1 Постановка задачи

3.2 Модифицированный проекционный переобуславливатель

3.3 Алгоритм построения блока V

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

4 Алгебраический многосеточный метод для трехмерных задач, дискре-тизированных на сетках, состоящих из призм

4.1 Постановка задачи

4.2 Оценка параметра а

4.3 Алгоритм построения блоков

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

5 Применение АММИ для решения задач теории упругости

5.1 Постановка задачи

5.2 Стандартная конечно-элементная дискретизация

5.3 Дискретизация на основе смешанной формулировки

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

Введение диссертации (часть автореферата) на тему «Алгебраические многосеточные методы для задач с малым параметром»

Введение

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

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

Использованию итерационных методов в вычислительной практике посвящена обширная литература. Подробное изложение теории итерационных методов можно найти, например, в работах [14], [17], [21], [25]. Простейшими итерационными методами являются метод Ричардсона, метод Якоби, метод Гаусса-Зейделя, а также метод последовательной верхней релаксации. Для класса алгебраических систем, порождаемых конечно-элементной дискретизацией эллиптических уравнений второго порядка, скорость сходимости упомянутых выше итерационных методов зависит от параметра дискретизации к (размера шага дискретизационной сетки) и значительно ухудшается при стремлении И, к нулю. Скорость сходимости основных итерационных методов можно существенно улучшить, применив к ним процедуры ускорения, такие как чебышевское ускорение или ускорение по методу сопряжённых градиентов. У каждой из упомянутых процедур ускорения есть свои достоинства и недостатки. Реализация чебышевского итерационного метода более проста, при его использовании не требуется вычисления скалярных произведений, что наиболее ценно при проведении рассчетов на параллельных компьютерах. С другой стороны, существенным недостатком чебышевского итерационного метода является необходимость иметь достаточно хорошие оценки границ спектра матрицы, которые, как правило, недоступны. Поэтому метод сопряжённых градиентов является одним из наиболее привлекательных методов для решения систем линейных алгебраических уравнений с симметричными положительно определёнными (и полуопределёнными) матрицами.

И для чебышевского метода, и для метода сопряжённых градиентов скорость сходи-

мости существенно зависит от спектральных свойств итерируемой матрицы. Как известно (см. [3], например), приближенное решение хд., полученное с использованием метода сопряженных градиентов, удовлетворяет следующим оценкам:

||х - XfclU <2ак ||х - х0||а, ||х - х*||2 < 2 ||х - х0||2,

где х — точное решение, а = (л/к - 1)/(у/к+ 1), а к = Amax(A)/Amin(A) — спектральное число обусловленности матрицы системы. Аналогичная оценка справедлива также и для чебышевского итерационного метода:

||x-Xfc||2 < 2ak ||х — Хо||г-

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

Ах -Ъ

рассматривается система

М~1Ах = М~гЬ (либо, альтернативно, система АМ~ху — b, х = М-1 у)

с матрицей М, выбранной таким образом, что, с одной стороны, обращение M легко реализуемо и, с другой стороны, число обусловленности матрицы М~гА значительно меньше числа обусловленности исходной матрицы А. Для достижения скорости сходимости, не зависящей от параметров рассматриваемой алгебраической задачи (в том числе не зависящей от шага h дискретизационной сетки) необходимо построить спектрально эквивалентный переобуславливатель M такой, что к(М~1А) < Const. Для обеспечения приемлимых арифметических затрат при решении возникающих в современной вычислительной практике систем большой размерности (где количество неизвестных достигает сотен тысяч и даже миллионов) желательно также, чтобы стоимость умножения на переобуславливатель росла не более чем линейно с ростом размерности задачи.

При решении самосопряжённых эллиптических задач одним из возможных способов построения переобуславливателей, удовлетворяющих указанным выше требованиям, является использование многосеточных методов. Впервые многосеточный метод был предложен Р. П. Федоренко в работах [19] и [20], где была рассмотрена итерационная процедура решения уравнения Пуассона и был доказан оптимальный порядок ее вычислительной сложности. Исследование скорости сходимости многосеточного метода для разностных эллиптических операторов второго порядка с переменными коэффициентами было проведено Н. С. Бахваловым [2]. Для случая конечно-элементной аппроксимации эллиптического уравнения сходимость многосеточного метода была доказана Н. Г. Астраханцевым [1]. Среди первых работ, посвященных данной тематике, отметим также работы [13], [15], где В. И. Лебедевым был предложен KP-метод, близкий по своей структуре к многосеточным методам. В дальнейшем интерес к многосеточным методам начал стремительно нарастать. Упомянем следующие работы, внесшие существенный вклад в развитие теории многосеточных методов: W. Hackbusch [63], [64], [65]; A. Brandt [57], [58]; D. Braess [49], [50], [51]; R. Е. Bank, T. Dupont [43], [44], [45]; S. McCormick [77], [78], [79]; J.-F. Maître,

F. Musy [72], [73]; H. Yserentant [93], [94]; В. В. Шайдуров [22], [23], [24]; J. H. Bramble, J. E. Pasciak, J. Xu [55], [56]; O. Axelsson, P. Vassilevski [37], [38]; Ю. А. Кузнецов [66], [68], [69], [74]. Систематическое изложение теории многосеточных методов может быть найдено в монографиях [24], [52], [65], [88].

При исследовании скорости сходимости "классических" многосеточных методов существенно используется предположение о регулярности рассматриваемой дифференциальной задачи. Как было показано в работах [42] и [49], если дифференциальная задача имеет решение из Н2 для любой правой части из L^ то при использовании многосеточного метода типа F-цикла в качестве переобуславливателя итерационный процесс является сходящимся, при этом скорость сходимости не зависит от числа используемых уровней (от размерности решаемой алгебраической системы). Этот результат был в дальнейшем обобщён в [53], [60] на случай //^"-регулярных задач, 0 < а < 1. Независимость скорости сходимости многосеточного метода по типу W-цикла от числа уровней была доказана в работах [43] и [65] в предположении Нх +а-регулярности решения.

Одним из подходов к построению многосеточных методов, не опирающихся на какие-либо предположения о регулярности задачи, является построение переобуславливателей, основанных на двухуровневом разбиении сеточных функций. Алгоритм такого типа был рассмотрен в [26], [27], [72], а также в ряде других работ. На основе метода, предложенного в этих работах, Н. Yserentant [93] перешёл от двухуровневого разбиения к многоуровневому, т.е. к многосеточным переобуславливателям. В данном подходе (а также в его модификации, предложенной в [44]) используется метод конечных элементов с так называемыми иерархическими базисными функциями. Для метода конечных элементов с использованием классического "нодального" базиса многосеточный метод такого типа был предложен в работе [89]. Эти методы являются близкими к оптимальным для двумерных задач (в том смысле, что число обусловленности матрицы М~1А растёт как log Л,-1 или log2 h~l при h —> 0). Однако, они не являются достаточно эффективными при решении трёхмерных задач: число обусловленности растет как h~l.

Подход к стабилизации числа обусловленности данного класса многосеточных переобуславливателей был разработанн в работах [37], [38] (О. Axelsson и P. Vassilevski). Доказательство сходимости предложенного в этих работах алгебраического метода многоуровневых итераций (АММИ) опирается на использование алгебраического аналога так называемого усиленного неравенства Коши-Буняковского; стабилизация числа обусловленности достигается посредством рекурсивного использования в методе внутренних чебышевских итераций. Важной особенностью данного переобуславливателя является то, что он оптимален (или близок к оптимальному) по отношению как к скорости сходимости итерационного процесса, так и к вычислительным затратам на его реализацию; при чем это справедливо вне зависимости и от регулярности задачи, и от разрывности коэффициентов эллиптического оператора. Заметим также, что сходный многосеточный переобуславливатель, стабилизированный с помощью внутреннего чебышевского итерационного процесса, был независимо предложен Ю. А. Кузнецовым [9], [68], [69]. Интересной особенностью данного метода (MGDD переобуславливателя) является то, что его можно рассматривать и как многоуровневый метод разделения области [8], [70], и как многосеточный метод.

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

переобуславливателей такого типа является одной из главных целей проводимых нами исследований. Настоящая работа посвящена построению итерационных алгоритмов, скорость сходимости которых слабо зависит от "малого параметра" в задаче. Примером такого "малого параметра" может быть либо минимальный угол в используемой триангуляции, либо коэффициент анизотропии в тензоре диффузии, либо степень "вытяну-тости" области, в которой поставлена задача. При построении методов, устойчивых по отношению к "малому параметру" нами будет существенно использована техника, разработанная в [26], [37] и [38]. В связи с этим предлагаее алгоритмы могут быть отнесены к классу алгебраических методов многоуровневых итераций (АММИ), предложенных в указанных выше работах.

Настоящая диссертация состоит из Введения и пяти глав. В Главе 1 изложены основные подходы к постоению АММИ переобуславливателей. В частности, рассматриваются мультипликативный и аддитивный способы построения двухуровневого пе-реобуславливателя, а также подходы к стабилизации скорости сходимости метода в многоуровневом случае. В Главе 2 предлагается специальная модификация аддитивного АММИ, устойчивая по отношению к анизотропии. Одной из новых идей, используемых при построении метода, является особый выбор аппроксимаций В^ к блокам А^, возникающих при 2x2 блочном разбиении матриц жесткости А^ на каждом из уровней дискретизации:

А\ о I } "новые" базисные функции _

} "старые" базисные функции ' о, ■ ■ ■,

АЮ =

41 л12

А(к) А{к) Л21 л22

В настоящей работе предлагается строить аппроксимации В^ путем сохранения единственной (максимальной по модулю) внедиагональной связи в каждой из суперэлементных матриц жесткости, соответствующих блоку . Данный подход является развитием похожей идеи, предложенной ранее в [75]. Важной собенностью разработанной методики является то, что при использовании специального упорядочения неизвестных матрицы , полученные с помощью алгоритма, имеют блочно-диагональную структуру и могут быть обращены с арифметическими затратами, пропорциональными их размерности.

Как будет показано в дальнейшем, число обусловленности к при этом огра-

ничено независимо как от параметров сетки, так и от анизотропности коэффициента эллиптического оператора:

ав иМР Ч < -Ь=«5.31.

15

Необходимо подчеркнуть, что предлагаемый алгоритм позволяет конструировать матрицы ВЙ} автоматически, при этом не накладывается никаких ограничений на выбор триангуляции самого грубого уровня. Это является основным преимуществом разработанного подхода по сравнению с подходом, предложенным в [75]. Разработанный алгоритм может быть также использован в случае билинейной конечно-элементной дискретизации на декартовых сетках. И в этом случае, сохраняя только самые сильные связи в локальных суперэлементных матрицах жесткости, можно построить легко обращаемые спектрально эквивалентные аппроксимации к блокам . Другой новой идеей, используемой

при построении устойчивого по отношению к анизотропии многосеточного метода, является использование проекционного переобуславливателя при решении задач на самой грубой сетке. Этот вопрос будет подробно рассмотрен в главе 3, где будет предложен эвристический алгоритм решения существенно анизотропных задач диффузии. В основу предлагаемой методики положена техника окаймления [18], [33] со специальным выбором окаймляющих векторов. Заметим, что предлагаемая итерационная процедура по своей сути близка к так называемому "дефляционному" методу сопряженных градиентов, предложенному в [81], но имеет при этом более низкую арифметическую сложность и лучшие параллелизационные свойства. В Главе 4 разработан легко параллелизуемый переобуславливатель для трехмерных эллиптических задач второго порядка, дискрети-зированных на конечно-элементных сетках, состоящих из прямоугольных призм. Особенностью предлагаемого алгоритма является специальное расщепление оператора задачи, используя которое удается построить многосеточный итерационный процесс, скорость сходимости которого ограничена независимо от разрывов в коэффициенте задачи. Глава 5 посвящена применению разработанных многосеточных переобуславливателей к задачам теории упругости.

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

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

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

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

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

• Создан пакет программ, реализующих различные варианты алгебраических многосеточных методов, в том числе и на параллельных ЭВМ.

По результатам работы имеется восемь публикаций [16], [34], [35], [36], [83], [84], [85], [86], пять из них с соавторами. Основные результаты диссертации были представлены на следующих конференциях:

• международная конференция по многосеточным методам "AMLI-96", г.Наймеген, Голландия, 14-16 июня 1996 г., сделан доклад " О стабилизированном аддитивном алгебраическом методе многоуровневых итераций";

• международная конференция "Preconditioned Iterative Solution Methods for Large-Scale Problems in Scientific Computations", г.Наймеген, Голландия, 27-29 мая 1997 г., сделан доклад "Об итерационном методе решения анизотропных эллиптических задач";

• конференция Молодых ученых, Новосибирск, 20-22 апреля 1998 г., сделан доклад "Модельный анализ приближенного варианта метода окаймления";

• международный семинар "Iterative Processes for Solving Equations", г.Киль, Германия, 3-5 июля 1998 г., сделан доклад "Об эффективном параллельном методе решения задач теории упругости";

• международная конференция " Mathematical Modelling and Computational Methods in Mechanics and Geodynamics", г.Прага, Чехия, 7-11 июля 1998 г., сделан доклад "О многосеточном алгоритме решения задач теории упругости, скорость сходимости которого не зависит от регулярности используемых дискретизационных сеток";

• международная конференция "Iterative Solution Methods for the Elasticity Equations as Arising in Mechanics and Biomecanics", г.Наймеген, Голландия, 28-30 сентября 1998 г., сделан доклад "О параллельном многоуровневом методе для итерационного решения задач теории упругости";

а также на семинарах Института вычислительной математики РАН, семинарах Франко-Русского центра им.Ляпунова, семинарах в университете г. Ювяскюла (Финляндия) и в университете г. Наймегена (Голландия).

Автору хотелось бы выразить глубокую благодарность своему научному руководителю проф. Ю.А.Кузнецову за постановку задачи, постоянную поддержку и внимание к работе, а также проф. O.Axelsson из университета г.Наймегена (Голландия) за многочисленные консультации и предоставленную возможность проведения параллельных экспериментов на многопроцессорных ЭВМ Cray ТЗЕ-600 и SUN ES-4000. Кроме того, хотелось бы поблагодарить А.А.Загумённых и всех сотрудников лаборатории вычислительной математики ИВМ РАН за теплую дружескую атмостферу и многочисленные полезные дискуссии. Также хотелось бы поблагодарить группу ученых из лаборатории численного анализа университета г.Наймегена за атмосферу благоприятствования при проведении исследований во время моих коммандировок в Голландию. В заключение автору хотелось бы выразить глубокую признательность своей жене, Ю.О.Падий, за неоценимую моральную поддержку и помощь при написании настоящей диссертации.

Список литературы диссертационного исследования кандидат физико-математических наук Падий, Александр Викторович, 1998 год

Литература

[1] Астраханцев Г. П. Об одном итерационном методе решения сеточных эллиптических задач // Журн. выч. мат. и мат. физики. - 1971. - т. 11. - N2.

- с. 439-448.

[2] Бахвалов Н. С. О сходимости одного релаксационного метода при естественных ограничениях на эллиптический оператор // Журн. выч. мат. и мат. физики. -1966. - т. 6. - N5. - с. 861-883.

[3] Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. - М.: Наука, 1984.

[4] Гловинский Р, Лионе Ж.-Л., Тремольер Р. // Численное решение вариационных неравенств. - М.: Мир, 1979.

[5] Ильяш Ю. И. Алгебраические многосеточные методы и их приложения к модельным задачам вычислительной гидродинамики // Дисс. канд. ф.-м. наук, 01.01.07, Москва, 1996, 119 с.

[6] Кобельков Г. М. Об эквивалентных нормировках подпространств Ь2 // Analysys Matheraatica. - 1977. - No. 3. - с. 177-186.

[7] Кобельков Г. М. О численных методах решения уравнений Навье Стокса в переменных скорость-давление // В сб. Вычислительные процессы и системы, 8

- М., Наука, 1991.

[8] Кузнецов Ю. А. Многоуровневые методы разбиения области. - В кн.: Численный анализ и математическое моделирование. - М., ОВМ АН СССР, 1989. - с. 1-52.

[9] Кузнецов Ю. А. Алгебраические многосеточные методы декомпозиции области. -М., ОВМ АН СССР, 1989. - 41 с. /Препринт 232/

[10] Ладыженская О. А. Математические вопросы динамики вязкой несжимаемой жидкости. - М.: Наука, 1970.

[11] Лебедев В. И. Метод ортгональных проекций для конечноразностного аналога одной системы уравнений // ДАН СССР. - 1957. - т. 113, N 6.

[12] Лебедев В. И. Разностные аналоги ортогональных разложений, основных дифференциальных операторов и некоторых краевых задач математической физики. I, II // Журн. выч. мат. и мат. физики. - 1964. - NN 3, 4 - с. 449-465, 649659.

[13] Лебедев В. И. Об итерационном КР-методе // Журн. выч. мат. и мат. физики. -1967. - т. 7, N 6.

Марчук Г. И. Методы вычислительной математики. - М.: Наука, 1980. - 536 с.

Марчук Г. И., Лебедев В. И. Численные методы в теории переноса нейтронов. М.: Атомиздат, 1981.

Ларин М. Р., Падий А. В., Модельный анализ приближенного варианта метода окаймления // Труды Конференции Молодых Ученых, Новосибирск, 20-22 апреля, 1998, Издательство ИВМиМГ СО РАН, Новосибирск.

Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений. - М.: Наука, 1978. - 592 с.

Фаддеев Д К., Фаддеева В. Н. Вычислительные методы линейной алгебры - Государственное издательство физико-математической литературы, Москва-Ленинград, 1963.

Федоренко Р. П. Релаксационный метод решения разностных эллиптических уравнений // Журн. выч. мат. и мат. физики. - 1961. - т. 1. - N5. - с. 922-927.

Федоренко Р. П. Скорость сходимости одного итерационного процесса // Журн. выч. мат. и мат. физики. - 1964. - т. 4. - N5. - с. 559-564.

Хейгеман Л., Янг Д. Прикладные итерационные методы - М.: Мир, 1986. - 448 с.

Шайдуров В. В. Проекционно-сеточные схемы на последовательности сеток // Вычислительные методы линейной алгебры. - М.: ОВМ АН СССР, 1983. - с. 238246.

Шайдуров В. В. Многосеточные итерационные алгоритмы решения сеточной цтационарной задачи Стокса // В сб. Вычислительные процессы и системы, 6 -М., Наука, 1988. - с. 264-270.

Шайдуров В. В. Многосеточные методы конечных элементов. - М.: Наука, 1989. -288 с.

Axelsson О. Iterative Solution Methods. - Cambridge University Press, New York, 1994.

Axelsson O., Gustafsson I. Preconditioning and two-level multigrid methods of arbitrary degree of approximation. - Math. Сотр. - 1983. - v. 40. - pp. 219-242.

Axelsson 0. On multigrid methods of the two-level type. - In: Multigrid Methods, Proceedings, Koln-Porz, 1981, (W. Hackbush and U. Trottenberg, eds.) LNM 960, Springer, 1982. - pp. 352-367.

Axelsson O., Stabilization of AMLI methods; additive methods, in Proc. Conf. on Algebraic Multilevel Iteration Methods with Applications, Axelsson O. and Polman В., eds., University of Nijmegen, The Netherlands, 1996, pp. 49-62.

Axelsson O., The stabilized V-cycle method, J. Сотр. Appl. Math., 74(1996), pp. 33-50.

[40 [41 [42

Axelsson O., An algebraic framework for hierarchical basis functions multilevel methods or the search for "optimal" preconditioners, in Iterative Methods for Large Linear Systems, D. Kincaid and L. Hayes, eds., Academic Press, New York, 1990, pp. 17-40.

Axelsson O., Barker V., Finite Element Solution of Boundary Value Problems, Theory and Computation. - Academic Press, Orlando, Florida, 1984.

Axelsson O., Neytcheva M., Algebraic multilevel iteration method for Stieltjes matrices. - Num. Lin. Alg. Appl., 1(1994), pp. 213-236.

Axelsson O., Neytcheva M., Polman B., The bordering method as a preconditioning method. - Technical report No 9348, University of Nijmegen (1993).

Axelsson O., Padiy A., On the additive version of the algebraic multilevel iteration method for anisotropic elliptic problems. - preprint No 9711, University of Nijmegen, 1997, to appear in SIAM J. Sci. Comput.

Axelsson O., Padiy A., On a robust and scalable linear elasticity solver based on a saddle point formulation. - preprint No 9723, University of Nijmegen, 1997, to appear in Int. J. Num. Meth. Eng.

Axelsson O., Georgiev K., Mellaard M., Neytcheva M., Padiy A., Scalable and optimal iterative solvers for linear and nonlinear problems. - preprint No 9613, University of Nijmegen, 1996.

Axelsson O., Vassilevski P. Algebraic multilevel preconditioning methods, I. - Numer. Math. - 56 (1989) - pp. 157-177.

Axelsson O., Vassilevski P. Algebraic multilevel preconditioning methods, II. - SIAM J. Numer. Anal. - 27 (1990) - pp. 1569-1590.

Axelsson 0., Vassilevski P., A black-box generalized conjugate gradient solver with inner iterations and variable-step preconditioning. // SIAM J. Matrix Anal. Appl., 12(1991), pp. 625-644.

Axelsson 0., Vassilevski P., Variable-step multilevel preconditioning methods. - Numer. Linear Alg. Appl. - 1 (1994) - pp. 75-101.

Babuska I., Suri M., Locking effects in the finite approximation of elasticity problems, Numer. Math. 62, 1992, pp.439-463.

Bank R. E., Douglas C. Sharp estimates for multigrid rates of convergence with general smoothing and acceleration // SIAM J. Numer. Anal. - v. 22, pp. 617-633.

Bank R. E., Dupont T. An optimal order process for solving elliptic finite element equations // Mathematics of Computation. - 1981. - v. 36. - pp. 35-51.

Bank R.E., Dupont T., Yserentant H. The hierarhical basis multigrid methods // Numer. Math. - 1988. - v. 52. - pp. 427-458.

Bank R. E., Dupont T. Analysis of a two-level scheme for solving finite element equations. - 1980. - (Report / Center for Numerical Analysis, The University of Texas at Austin; CNA-159). pp. 35-51.

Bank R., Dupont T., Yserentant H., The hierarchical basis multigrid method. // Numer. Math. - 52 (1988) - pp. 427-458.

Bank R. E., Welfert B. D., Yserentant H. A class of iterative methods for solving saddle point problems // Numer. Math. 1990. - v. 56. - pp. 645-666.

Braess D. The contraction number of a multigrid method for solving the Poisson equation // Numer. Math. - 1981. - v. 37. - pp. 387-404.

Braess D., Hackbush W. A new convergence proof for the multigrid method including the V-cycle // SIAM J. Numer. Anal. - 1983. - v.20, N5. - pp. 967-975.

Braess D. The convergence rate of a multigrid method with Gauss-Siedel relaxation for the Poisson equation // Mathematics of Computation. - 1984. v. 42. - pp. 505-519.

Braess D. On the Combination of the Multigrid Method and Conjugate Gradients // Lect. Notes, in Math. - 1985. - 1228. - p. 52-64.

Bramble J. H. Multigrid Methods. - Pitman Research Notes in Mathematics Series, Longman Scientific & Technical, London. (Copublished with John Wiley & Sons, Inc., New York), 1993.

Bramble J. H., Pasciak J. E. New convergence estimates for multigrid algorithms // Math. Comp. - 1987. - v. 49. - pp. 311-329.

Bramble J. H., Pasciak J. E. A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems // Math. Comp. 1988. - 181. - pp. 1-17.

Bramble J. H., Pasciak J. E., Xu J. Parallel multilevel preconditioners // Math. Comp. - 1990 - 55. pp. 1-22.

Bramble J. H., Pasciak J. E., Convergence estimates for multigrid algorithms without regularity assumptions // Math. Comp. - 1991 - 57. - pp. 23-45.

Brandt A. Multi-level adaptive technique (MLAT) for fast numerical solution to boundary value problem // Lect. Notes, in Phys. - 1972. - v. 18. - p. 82-89.

Brandt A. Multi-level adaptive solution to boundary value problems // Mathematics of Computation. 1977. - v. 31. - p. 333-390.

Brezzi F., Fortin M., Mixed and Hybrid Finite Elements Methods. // Springer Verlag, New York, 1991.

Decker N. H., Mandel J., Parter S. V. On the role of regularity in multigrid methods. -In: Multigrid Methods, Theory, Applications and Supercomputing, (S. McCormic, ed.) Marcel Dekker, New York, 1988.

Eijkhout V., Vassilevski P., The role of the strengthened Cauchy-Bunyakowski-Schwarz inequality in multilevel methods, SIAM Rev., 33(1991), pp. 405-419.

Georgiev A., Baltov A. and Margenov S., HIPERGEOS benchmark problems related to bridge engineering applications, project report COP-94-Q820-MOST-4.

Hackbush W. Survey of convergence proofs for multigrid iterations. // Special Topics of Applied Mathematics (Ed. J. Frehse). - Amsterdam, 1980. - pp. 151-164. - pp. 177-210.

Hackbush W. Multigrid convergence theory // Lect. Notes in Math. - 1982. - pp. 177210.

Hackbush W. Multigrid methods and applications. Springer-Verlag, Berlin Heidelberg - New York, 1985.

Hakopian Yu. R., Kuznetsov Yu. A. Algebraic multigrid / substructuring preconditioned. - Sov. J. Numer. Anal. Math. Modelling, v. 6, pp. 453-483 (1991).

Kobel'kov G. M., Valedinskiy V. D. On the inequality ||p||z,2 < cll^pH^-i and its finite dimensional image. Sov. J. Numer. Anal. Math. Modelling, v. 1, pp. 189 201 (1986).

Kuznetsov Yu. A. Multigrid domain decomposition methods for elliptic problems. - In: Proceedings of VIII Intern. Conf. on Comput. Meth. for Applied Science and Engineering, 1987. v. 2. - pp. 605-616.

Kuznetsov Yu. A. Algebraic Multigrid Domain Decomposition method. - Sov. J. Numer. Anal. Math. Modelling, v. 4, pp. 351-380 (1989).

Kuznetsov Yu. A. Multi-level domain decomposition methods // Appl. Num. Math. -v. 6., 1989/90 - pp. 303-314.

Lanczos C. Solution of the systems of linear equations by minimized iterations //J. Res. Nat. Bur. Stand. - 1952. - 49. - pp. 33-53.

Maitre J.-F., Musy F. The construction number of a class of two-level methods: an exact evaluation for some finite element subspaces and model problems. - In: Multigrid Methods, Proceedings, Koln-Porz, 1981, (Eds. W. Hackbush and U. Trottenberg) LNM 960, Springer, 1982. - pp. 535-544.

Maitre J.-F., Musy F. Multigrid methods: Convergence theory in a variational framework // SIAM J. Numer. Anal. - 1984. - v. 21. - pp. 657-671.

Marchuk G. I., Kuznetsov Yu. A., Matsokin A. M. Fictitious domain and domain decomposition methods. - Sov. J. Numer. Anal. Math. Modeling, v. 1, 3-35 (1986).

Margenov S., Vassilevski P., Algebraic multilevel preconditioning of anisotropic elliptic problems. - SIAM J. Sci. Comput., v. 15, 1026-1037 (1994).

Margenov S., Xanthis L., Zikatanov L On the optimality of the semi-coarsening AMLI algorithm, in Proc. of the 2nd IMACS symposium on Iterative Linear Algebra, Blago-evgrad, 1995.

McCormick S. F., Ruge J. Multigrid methods for variotional problems // SIAM J. Numer. Anal. - 1982. - v. 19. - pp. 924-928.

McCormick S. F. Multigrid methods for variotional problems: Further results. // SIAM J. Numer. Anal. - 1984. - v. 21. - pp. 255-263.

[79] McCormick S. F. Multigrid methods for variotional problems: General theory. // SIAM J. Numer. Anal. - 1985. - v. 22. - pp. 634-643.

[80] Mikhlin S., The problem of the minimum of a quadratic functional, Holden -Day Inc., San Francisco, 1965.

[81] Nicolaides R. Deflation of the conjugate gradient method with applications to boundary value problems // SIAM J. Numer. Anal. - 1987. - v. 10. - pp. 355-365.

[82] Ong. M. Hierarchical basis preconditioners in three dimensions, SIAM J. Sci. Comp., to appear.

[83] Padiy A., Multilevel iterative method for anisotropic elliptic problems // In: Proceedings of the Conference on Preconditioned Iterative Solution Methods for Large Scale Problems in Scientific Computations "PRISM-97", University of Nijmegen, May 27-29, 1997, pp. 145-169.

[84] Padiy A., On a robust multilevel method applied for solving large-scale linear elasticity problems. - preprint No 9806, University of Nijmegen, 1998, to appear in Comm. Num. Meth. Eng.

[85] Padiy A., On a parallel multilevel solver for linear elasticity problems, 1998, Internal HIPERGEOS report, submitted.

[86] Padiy A., Larin M. Model analysis of a subspace correction technique for anisotropic diffusion problems, preprint No 9818, University of Nijmegen, 1998, submitted.

[87] A. Quarteroni, A. Valli, Numerical Approximation of Partial Differential Equations, Springer Verlag, New York, 1994.

[88] Stuben K., Trottenberg U. Multigrid methods: Fundamental algorithms, model problem analysis and applications. // Lect. Notes in Math. - 1982. - pp. 1-176.

[89] Vassilevski P. Nearly optimal iterative methods for solving finite element elliptic equations based on the multilevel splitting of the matrix. - Report 1989-9, Institute for Scientific Computation, The University of Wyoming, Laramie, USA, 1989.

[90] Vassilevski P., On two ways of stabilizing the hierarchical basis multilevel methods. -SIAM Rev., 39(1997), pp. 18-53.

[91] Vassilevski P. Hybrid V-cycle algebraic multilevel preconditioners. - Math. Comp. - 58 (1992) - pp. 489-512.

[92] Xu. J. Iterative methods by space decomposition and subspace correction // SIAM Review. - 1992. - v. 34. - pp. 581-613.

[93] Yserentant H. On the multi-level splitting of finite element spaces // Numerishe Mathematik. - 1986. v. 49. - N4. - pp. 379-412.

[94] Yserentant H. Two preconditioners based on the multi-level splitting of finite element spaces // Numerishe Mathematik. - 1990. - v. 58. - N1. - pp. 163-184.

[95] O. Zienkiewicz, Y. Liu and G. Huang, Error estimates and convergence rates for various incompressible elements, Int. J. Numer. Meth. Eng. 28, 1989, pp.2191-2202.