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

• Мацех, Анна Михайловна
• кандидат физико-математических наук
• 2007

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

Оглавление

Введение

Глава 1 Современное состояние исследований

1.1 Алгебраическая проблема собственных значении.

1.2 Сингулярное разложение .1С

1.3 Проблема Уилкинсона.

1.4 Последовательности Штурма.

1.5 Методы определения спектральных и сингулярных характеристик и их реализация.

1.0 Выводы и постановка задачи.

Глава 2 Методы бисекций и обратной итерации с оцениваемой точностью

2.1 Метод бисекций с оцениваемой точностью.

2.2 Метод обратной итерации с оцениваемой точностью.

2.2.1 Определение собственного вектора

2.2.2 Выбор сдвига.

2.2.3 Определение начальных векторов

2.2.4 Расчет нескольких собственных векторов.

2.3 Выводы.

Глава 3 Метод Ланцоша с оцениваемой точностью

3.1 Особенности реализации.

3.2 Алгоритм определения собственных чисел

3.3 Особенности расчета сингулярных чисел

3.4 Алгоритм определения сингулярных чисел.

3.5 Выводы.

Глава 4 Библиотека Sturm

4.1 Общая характеристика

4.2 Вычислительные схемы.

4.3 Верификация и вычислительный эксперимент.

4.3.1 Полное спектральное разложение.

4.3.2 Частичное спектральное разложение.

4.3.3 Частичное сингулярное разложение.

4.4 Выводы.

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

Актуальность работы

Проблема разработки быстрых алгоритмов, гарантирующих точность при определении спектральных и сингулярных характеристик матриц конечно-разностных и конечно-элементных аппроксимаций дифференциальных операторов, является центральной проблемой современной вычислительной алгебры. Знание спектральных характеристик необходимо при решении задач моделирования электромагнитных полей |40, 3|, в задачах структурной механики [5, 21|, ядерной физики, квантовой химии, при решении задач, описывающих свойства диэлектрических волноводов, при анализе океанографических моделей и во многих других приложениях математической физики [47, 59]. Сингулярное разложение (БУБ) используется для распознавания, сжатия и восстановления изображений в компьютерной графике, а в генетике и биологии позволяет делать выводы о эволюции генов и связях между протеинами. Знание нулевых сингулярных чисел произвольной матрицы позволяет определить ее ранг, а также необходимо для построения обобщенного нормального решения систем уравнений, у которых число уравнений не совпадает с числом неизвестных.

Сложность определения спектральных и сингулярных характеристик матриц, возникающих при моделирования физических процессов как правило обусловлена необходимостью определения близких, почти кратных собственных значений и соответствующих им почти коллинеарных собственных векторов, при расчете которых стандартными вычислительными методами наблюдается медленная сходимость, обусловленная потерей ортогональности и точности. Не менее важной является проблема реали-л' зации методов определения спектральных и сингулярных характеристик в виде библиотек подпрограмм и прикладных пакетов для современных вычислительных систем. Первая широко известная библиотека подпрограмм для решения задач на собственные значения - Е1ЭРАСК [70] - была разработана в середине 70-х годов. На смену ей пришла библиотека подпрограмм ЬАРАСК [1, 15], представляющая собой набор процедур, реализующих алгоритмы решения задач линейной алгебры с плотными, трех- и двухдиагональпыми матрицами. Одной из наиболее распространенных современных библиотек предназначенных для определения спектральных и сингулярных характеристик матриц большой размерности является библиотека А11РАСК [45]. Среди современных пакетов прикладных программ, позволяющих решать задачи на собственные значения и задачу определения спектрального разложения, отметим пакет МаЫаЬ [75]. При определении спектрального и сингулярного разложений пакет Ма11аЬ вызывает откомпилированные модули из библиотек ЬАРАСК и А11РАСК, при этом все вычисления производятся в стандартной модели арифметики 1ЕЕЕ-754 [2, 62, 48]. Точность в перечисленных комплексах программ не гарантируется.

В основе современных методов определения спектральных и сингулярных характеристик с гарантированной точностью лежат работы С.К. Годунова, А.Г. Антонова, О.П. Киршпока, В.И. Костина и А.Д. Митчен-ко [84, 83, 28]. В методах с гарантированной точностью используется элементы интервального анализа и специально разработанная модель арифметики с направленным округлением. Помимо приближенных собственных чисел, в методах с гарантированной точностью используются наименьшие машинно-нредставимые интервалы, гарантированно содержащие собственные значения рассматриваемой матрицы. Будем называть такие интервалы собственными интервалами. С.К. Годунов и др. строят численно ортогональную систему приближенных собственных векторов симметричной трехдиагоналыюй вещественной матрицы Т методом спектрального исчерпывания, применяя преобразования вращения, параметры которых строятся при помощи двусторонних последовательностей Штурма [84, 83, 82]. Двусторонняя последовательность Штурма иитериретпруется [60] как решение проблемы Уилкинсона [77] о корректном исключении уравнения из переопределенной системы уравнений Т х — Хх = 0. Индекс исключаемого уравнения в проблеме Уилкинсопа совпадает с индексом исключаемого элемента двусторонней последовательности Штурма. В силу высокой вычислительной сложности [GG] метод спектрального исчерпывания не приемлем для определения собственных и сингулярных векторов разреженных матриц большой размерности, возникающих в аппроксимациях дифференциальных операторов многих задач математической физики. Такие задачи решаются итерационными методами.

Метод Ланцоша [44, 58J является одним из наиболее эффективных итерационных методов решения симметричной проблемы собственных значений. В основе современных формулировок метода Ланцоша лежат работы Пэйджа [63, 04]. Существует несколько формулировок метода Ланцоша: с полной реортогонализациеп [31, 83], с выборочной и частичной реорто-гоиализацией [G], без реортогонализации [11, 37, 12, 80], с квазиминимизацией [27], с неявным перезапуском [71, G]. Метод Ланцоша с неявным перезапуском реализован в библиотеке ARPACK и применяется для определения спектрального и сингулярного разложений больших разреженных матриц. Метод Ланцоша с неявным перезапуском является вариантом метода. Арнольди с неявным перезапуском [71], в котором может происходить сходимость к ложным собственным значениям [23]. Вычислительный эксперимент показывает (см. раздел 4.3), что ложная сходимость возможна и в методе Ланцоша с неявным перезапуском. Реализация метода Ланцоша без реортогонализации в соответствии со схемой Коллум и Уилуби, называемая также методом Коллум-Уилуби-Ланцоша, позволяет идентифицировать ложные собственные значения и наиболее приемлема при работе с большими разреженными матрицами. Однако в методе Коллум-Уилуби-Ланцоша возможна ошибочная идентификация истинных почти кратных собственных значений как ложных, а скорость сходимости определяется спектральными свойствами задачи, в результате чего число внешних итераций может оказаться непредсказуемо большим.

Собственные векторы симметричных трехдиагональных матриц часто определяются методом обратной итерации, который имеет низкую вычислительную сложность порядка п2 при расчете хорошо обусловленного базиса из собственных векторов. При наличии почти кратных собственных значений метод обратной итерации требует дополнительной реортогона-лизации. М11ГШ, метод, или метод относительных робастпых представлений, является повой реализацией метода обратной итерации, в которой при выборе вектора начального приближения используется 'составная факторизация', представляющая собой альтернативное решение проблемы Уил-кинсона. МШ111 метод был впервые реализован без реортогонализации в библиотеке ЬАРАСК 3.0 в виде процедуры хЭТЕСЛ, имеющей сложность 0(п2). Нами установлено [52, 53], что в случаях, когда матрица имеет почти кратные собственные значения, соответствующие им собственные векторы вычисляются процедурой хЭТЕСИ, в ЬАРАСК 3.0 с недопустимо большими погрешностями. В версии ЬАРАСК 3.1 данная проблема решается включением выборочной реортогонализации в новую реализацию МШЖ метода.

В методе обратной итерации используются собственные значения, рассчитываемые методом бисекций, вычислительная сложность которого при расчете всех собств енпых значений составляет 5* ~ 2/с п арифметических операций [18], где к представляет собой число 7-ичных цифр мантиссы. В 1ЕЕЕ-754 модели арифметики с двойной точностью вычислительная сложность метода бисекций составляет Я « 106 п2, что почти в 10 раз медленнее С}11 метода в реализации, исключающей извлечение квадратных корней, вычислительная сложность которого составляет 5 ~ 12 п2 [18| арифметических операций.

Заметим, что проблемы, связанные с оптимальностью и точностью при определении спектральных и сингулярных характеристик, систематически исследовались в работах Хоффмаиа и Уайлаидта [35], Голуба и Кахана [29], Парлетта [05], Стюарта [72, 74], Кахана [13] и Деммела [14], Трефетена и Эмбри [70], Хайэма [33|, Князева [42, 43, 41], Малышева [40, 19]. Из недавних работ, посвященных определению собственных значений матриц большой размерности, отмстим работы Коллум [10, 8], Саада [08] и Сорспсе-на [45, 71].

Цель работы

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

Защищаемые положения

На защиту выносятся:

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

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

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

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

D методе обратной итерации с оцениваемой точностью

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

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

• новая вычислительная схема неполного спектрального исчерпывания используется при определении неколлинеарной системы векторов начального приближения, соответствующих почти кратным и численно кратным собственным значениям;

• вычислительная схема спектральной рекурсии используется для расчета вектора начального приближения, соответствующего изолированному собственному значению;

• расчет сингулярных векторов двухдиагональной вещественной матрицы сводится к расчету собственных векторов соответствующем! симметричной трехдиагопальной матрицы Голуба-Кахаиа.

В методе Ланцоша с оцениваемой точностью

• собственные интервалы используются для корректной идентификации истинных собственных значений; расчет собственных интервалов производится методом бисекций с оцениваемой точностью;

• метод обратной итерации с оцениваемой точностью применяется для оценки точности собственных и сингулярных чисел при расчете критерия останова итерационного процесса;

• метод обратной итерации с оцениваемой точностью применяется при расчете собственных и сингулярных векторов;

• частичная двухдиагонализация Голуба-Кахаиа-Ланцоша без реортогона-лизации применяется при расчете сингулярных характеристик несимметричных матриц, после чего решается эквивалентная частичная проблема собственных значений с матрицей Голуба-Кахаиа.

Практическая значимость работы

Алгоритмы, описывающие методы обратной итерации, Ланцоша и бисекций с оцениваемой точностью, были реализованы в виде программных модулей ANSI С библиотеки Sturm, реализованной в стандартной модели арифметики IEEE-754 с двойной точностью для операционной системы Linux. Библиотека Sturm является отчуждаемым программным комплексом, который может использоваться либо самостоятельно, либо может интегрироваться в другие библиотеки и комплексы программ. Библиотека Sturm предназначена для определения с оцениваемой точностью спектральных характеристик симметричных вещественных матриц и сингулярных характеристик несимметричных вещественных матриц дискретных аппроксимаций задач моделирования физических процессов. Вычислительный эксперимент демонстрирует высокую эффективность и точность программных модулей библиотеки Sturm.

Достоверность полученных результатов

Достоверность полученных результатов проверялась в ходе сравнительного анализа результатов решения задач моделирования физических процессов в библиотеке Sturm с результатами решения этих же задач в библиотеке LAPACK и пакете Matlab. Тестирование проводилось на матрицах, возникающих в конечно-разностных и конечно-элементных аппроксимациях задач моделирования конвективно-диффузионных процессов, на матрицах из наборов данных Matrix Market [59|, Harwell-Boeing [20|, NEP [7|, SPARSKIT [G9] и ТОКАМАК [59], возникающих в дискретных аппроксимациях задач структурной механики, океанографии, ядерной физики и электромагнетизма, а также на серии матриц большой размерности, генерируемых при решении задачи моделирования электрического ноля в нефтяной скважине векторным методом конечных элементов [94].

Апробация работы

Результаты проведенных исследований докладывались автором на семинаре С.К. Годунова 'Математика в приложениях' в ИМ СО РАН, на семинарах ИВМиМГ СО РАН и ИВТ СО РАН, на Всероссийской конференции по вычислительной математике 'КВМ-07' (Академгородок, Новосибирск, Россия, 2007г.) [93], на мииисимпозиуме 'Последние достижения в плотной линейной алгебре' в рамках конференции 'Современный уровень развития научных и параллельных вычислений' (Умеа, Швеция, 2006 г.) |54] по приглашению организаторов минисимпозиума; на 13-ой Конференции международного общества линейной алгебры (Амстердам, Нидерланды,

2000 г.) (55]; в виде технического доклада [53] по запросу группы разработчиков библиотеки ЬАРАСК; на Восьмой конференции по итерационным методам (Коппер Маунтейн, Колорадо, США, 2004 г.) [51]; на Восьмой конференции общества индустриальной и прикладной математики (Уильямс-бург, Вирджиния, США, 2003 г.) [57]; на Шестом международном симпозиуме но итерационным методам в научных вычислениях (третье призовое место в конкурсе статей аспирантов, Денвер, Колорадо, США, 2003 г.) [49]; па Международной конференции молодых ученых по математическому моделированию и информационным технологиям (Академгородок, Новосибирск, Россия, 2002 г.) [90]; па Конференции молодых ученых СО РАН, посвященной М.М. Лаврентьеву (Академгородок, Новосибирск, Россия,

2001 г.) [89]; на Международной конференции 'Современные проблемы прикладной математики и механики: теория, эксперимент и практика', посвященной 80-летию академика Н. Н.Яиепко (Академгородок, Новосибирск, Россия, 2001г.) [50]; на Конференции молодых ученых, посвященной 10-летию ИВТ СО РАН (Академгородок, Новосибирск, Россия, 2000г.) [88]; па XV конференции по интервальной математике в рамках конференции 'Вычислительные Технологии 2000' (ИВТ СО РАН, Академгородок, Новосибирск, Россия, 2000 г.) [91].

Публикации

По материалам диссертации опубликовано 10 работ, в том числе статья 15 рецензируемом журнале, рекомендованном ВАК для представления докторских диссертаций |92], статья в зарубежном рецензируемом журнале [52], статья в рецензируемом журнале СО РАН [50], а также; публикации [54, 55, 51, 57, 90, 50, 88] в трудах международных и российских конференций.

Личный вклад автора

В работе [92] автор участвовал в постановке задачи, автором лично разработаны и реализованы схема неполного спектрального исчерпывания, методы Ланцоша, бисекций и обратной итерации с оцениваемой точностью, проведен вычислительный эксперимент и написан первый вариант статьи. В работах [52, 50] автором лично разработан и реализованы метод Годунова-обратной итерации, проведен вычислительный эксперимент и написана статья. В публикациях [54, 55, 51, 90, 88] автором лично разработаны и реализованы представленные вычислительные схемы и алгоритмы, проведен вычислительный эксперимент, описаны результаты. В публикациях [57, 56] автор участвовал в постановке задачи, автором лично разработаны и реализованы представленные алгоритмы, проведен вычислительный эксперимент, описаны результаты.

Структура работы

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

Обозначения

• С" п-мерное комплексное евклидово пространство;

• Ж" п-мерное вещественное евклидово пространство;

• (со, С],., еп-\) - фиксированный ортопормированный базис в1", где еЛ = (0,.,0,^0,.,0)г, А; = 0,1,., п — 1; к+1

• х - (ж0, х\ ., хп~1)т - вектор х € (х Е Сп);

• (ж, у) = жт у скалярное произведение ж £ С" и у Е С";

• (ж, у) = хт у - скалярное произведение я Е К" и у Е К";

• ||а;|| = у/(х,у) - норма вектора х Е М™ (х Е С");

• С"хп - п-мерное комплексное векторное пространство;

• Мпхп - п-мерное вещественное векторное пространство;

• А = (а^), г,^ — 0,1,. ,п - 1 - матрица А Е М,гхп (А Е С'1ХИ);

• Ат = (ау?:), г, ,7 = 0,1,., п — 1 - транспонированная матрица А Е Шпхп ■>

• А* — (а^г), г, ,7 = 0,1,., п — 1 - комплексно-сопряженная транспонированная матрица А Е Спх?г;

• с^^ - диагональная матрица;

• I - единичная матрица в ШпХп (С/гхп)

• \iiii = Ао < А1 < • • • < Л,г1 = Ашах - собственные значения матрицы А Е Епхп {А Е Сих");

• 0 < (тт\п = сто < о"1 < - • • < <7„1 = <тшах - сингулярные числа матрицы

ЛеМ"*" (Ле€'да1);

• ||Л|| = о"пшх(Л) - спектральная норма матрицы А Е К7гх" (А Е Спхп);

• ^шасЬ ~ относительная погрешность машинного представления единицы в выбранной модели конечной арифметики;

• £шш ~ минимальное положительное машинное число в выбранной модели конечной арифметики;

• £шах ~ максимальное машинное число в выбранной модели конечной арифметики.

Заключение диссертации по теме «Вычислительная математика», Мацех, Анна Михайловна

4.4 Выводы

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

Заключение

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

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

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

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

• Разработана отчуждаемая ANSI С библиотека Sturm, программные модули которой реализуют методы бисекций, обратной итерации и Ланцоша с оцениваемой точностью в модели арифметики IEEE-754.

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

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

1. E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, D. Sorensen. LAPACK Users' Guide. S1.M, Philadelphia, third edition, 1999.

2. ANSI/IEEE. IEEE Standard for Binary Floating Point Arithmetic. New York, 7541985 edition, 1985.

3. P. Arbenz, R. Geus, S. Adam. Solving Maxwell eigenvalue problems for accelerating cavities. Physical Review Special Topics Accelerators and Beams, 4(022001), 2001.

4. Susanne Balk;, Jane Culluin. A parallel algorithm for c, omputing eigenvalues of very large real symmetric matrices on message passing architectures. Applied Numeriail Mathematics, 30:341 3G5, 1999. Theory.

5. F.L. Bauer, C.T. Fike. Norms and exclusion theorems. Numerische Math., 2:137 141, 1960.

6. Jane K. Cullum, Ralph A. Willoughby. Lanczos algorithms for large symmetric eigenvalue computations, volume 1. Society for Industrial and Applied Mathematics, Philadelphia, 2002.

7. J. Demmel, W. Kalian. Accurate singular values of bidiagonal matrices. SIAM J. Sci. Stat. Cornput., 11:873-912, 1990.

8. James Demmel. Accurate singular values decompositions of structured matrices. SIAM J. Matrix Anal. Appl, 21:502 580, 1999.

9. I.S. Dhillon, A.N. Malyshev. Inner deflation for symmetric tridiagonal matrices. Linear Algebra and its Applications, 358:139-141, 2003.

10. Juan C. Egana, Nelson M. Kuhl, Luis C. Santos. An inverse eigenvalue method for frequency isolation in spring-mass systems. Numerical Linear Algebra with Applications, 9(l):65-79, January/February 2002.

11. Siever Ellen, Inc. the staff of O'Reilly & Associates. Linux in a nutshell. O'Reilly k Associates, Inc., second edition, 1999.

12. Mark Embree. Misconvergence of Arnoldi Eigenvalue Iterations. 13-th International Linear Algebra Society Conference. Amsterdam, Netherlands, 2006. URL http:// staff.science.uva.nl/~brandts/ILAS06/.

13. J.G.F. Francis. The qr transformation: a unitary analogue to the lr transformation, parts i and ii. Com,put. ,/., 4:205-271, 332 345, 1961.

14. G. Golub, J. Wilkinson. Ill-conditioned eigensystems and the computation of the Jordan canonical form. SIAM Review, 18:578 619, 1976.

15. Gene H. Golub, Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 1996.

16. G.H. Golub, H.A. van der Vorst. Eigenvalue computation in the 20th century. Journal of Computational and Applied Mathematics, 123(1—2):35 65, 2000. Nicholas J. Higham. Accuracy and stability of numerical algorithms. SIAM, second edition, 2002.

17. R. Hiptmair. Finite elements in computational electromagnetism. Acta Numerica, 11:237- 339, 2002.

18. A.J. Hoffman, H.W. Wielandt. The variation of the spectrum of a normal matrix. Duke Math. J., 20:37 40, 1953.

19. Use C.F. Ipsen. Computing an eigenvector with inverse iteration. SIAM Review, 39(2):254-291, 1997.

20. Cullurn Jane, Willoughby Ralph A. Computing eigenvalues of very large symmetric matrices an implementation of a Lanczos algorithm with no reorthogonalization. Journal of Computational Physics, 44:329-358, 1981.

21. E.R. Jessup, I.C.F. Ipsen. Improving the accuracy of inverse iteration. SIAM Journal on Scientific and Statistical Computing, 13(2):550—72, 1992.

22. Cullum Jane K., Willoughby Ralph A. Lanczos algorithms for large symmetric eigenvalue computations. URL www.netXib.org, source code.

23. C. Lanczos. An iterative method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Standards, Sect. D, 45:255-282, 1950.

24. Osni Marques. Eigensolvers and applications in finite element analyses. Advanced Solution Procedures on Innovative Computer Architectures (M. Papadrakakis and G. Dugeda, Eds.), 6G 79, 1996.

25. A.M. Matsekh. The Godunov-inverse iteration algorithm for symmetric tridiagonal matrices. Bulletin of the Novosibirsk Computing Center. Series: Computer Science, (19) :39—50, 2003.

26. A.M. Matsekh. The Godunov-inverse iteration: a fast and accurate solution to the symmetric tridiagonal eigenvalue problem. Applied Numerical Mathematics, 54(2):208-221, 2005.

27. A.M. Matsekh. Numerical comparison of symmetric eigenvalue and SVD solvers basedon the two-sided Sturm sequences (Sturm library) and the corresponding LAPACK functionality. Technical report, Los Alamos National Laboratory, '2005. LA-UR-05-8-101.

28. Gerard Meurant, Zdenek Strakos. The lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numenca, 15:471-542, 2000.

29. National Institute of Standards and Technology. Matrix Market. URL http://math. nist.gov/MatrixMarket/, a visual repository of test data for numerical linear algebra.

30. J.C. Nedclec. Mixed finite elements in IR„ Numer. Math., 35:315-3-11, 1980.

31. J.M. Ortega, H.F. Kaiser. The Z/' and qr methods for symmetric tridiagonal matrices. Numer. Math., 5:211-225, 1963.

32. M. Overton. Numerical Computing with IEEE Floating Point, Arithmetic. SIAM, Philadelphia, PA, USA, 2001.

33. G3. C.C. Paige. Computational variants of the Lanczos method for the eigenproblem. Journal of the Institute of Mathematics and Its Applications, 10:373-381, 1972.

34. G4. C.C. Paige. Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix. Journal of the Institute of Mathematics and Its Applications, 18:3-11-349, 1976.

35. G5. Bcresford N. Parlett. The Symmetric Eigenvalue Problem. Prentice-Hall Inc., Englewood Cliffs, N.J, 1980.

36. G6. B.N. Parlett, I.S. Dhillon. Fernando's solution to Wilkinson's problem: An application of double factorization. Lin. Alg. Appl., 267:247-270, December 1997.

37. G7| B.N. Parlett, O.A. Marques. An implementation of the dqds algorithm (positive case).1.near Algebra and its Applications, 309:217-259, 2000.

38. Y. Saad. Numerical Methods for Large Eigenvalue Problems. Manchester University Press, Manchester, UK, 1992. URL http://www-users.cs.umn.edu/~saad/books. html.

39. Yousef Saad. SPAR.SKIT. URL http://www-users.cs.umn.edu/~saad/software/ SPARSKIT/sparskit.html, a basic tool-kit for sparse matrix computations.

40. B.T. Smith, J.M. Boyle, J.J. Dongarra, B.S. Garbow, Y. Ikebe, V.C. Klema, C.I3. Moler. Matrix Eigensystem Routines EISPACK Guide, volume 6 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1976.

41. Danny C. Sorensen. Numerical methods for large eigenvalue problems. Acta Numerica, 11(00) :519 584, 2002.

42. GAV. Stewart. Introduction to m,atrix computalions. Academic Press, New York, 1973. G.W. Stewart. On the early history of the singular value decomposition. SI AM Review, 35(4):551-56G, 1993.

43. G.W. Stewart. Matrix Algorithms, volume II, Eigensystems. G.W. Stewart, 1999. URL http://www.cs.umd.edu/~stewart.

44. J.II. Wilkinson. The Algebraic Eigenvalue Problem. Oxford University Press, 1965. J.H. Wilkinson. Rounding Errors in Algebraic Processes. Dover Publications, reprint edition, 1994.

45. Д.К. Фаддеев, В.II. Фаддеева. Вычислительные методы липейной алгебры,, 3-е стереотипное издание. Лань, Санкт-Петербург, 2002.

46. C.К. Годунов, Прокопов Г.П. Применение метода минимальных итераций для вычисления собственных значений эллиптических операторов. Журнал вычислительной математики и математической физики, 10(о): 1180 -1190, 1970.

47. С.К. Годунов. Совремеиные аспекты линейной алгебры. Новосибирск, Научная книга, 1997.

48. С.К. Годунов. Лекции по современным аспектам линейной алгебры. Новосибирск, Научная книга, 2002. Университетская серия, том 12.

49. С.К. Годунов, А.Г. Антонов, О.П. Киршпок, В.И. Костин. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Наука, Новосибирск, 1988.

50. С.К. Годунов, В.И. Костин, А.Д. Митченко. Вычисление собственного вектора симметричной трехдиагональной матрицы. Институт Математики СОАН СССР, Новосибирск, 1983. Препринт 44.

51. B.II. Кублановская. О некоторых алгоритмах для решения полной проблемы собственных значений. Журнал вычислительной математики и математической физики, 1(4):555 570, 1961.

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

53. В.П. Ильин. Методы, конечных разностей и конечных объем,ов для эллиптических уравнений. Новосибирск, Издательство Института Математики, 2000.

54. A.M. Мацех, Э.П. Шурина. Нахождение спектрального разложения симметричных матриц и сингулярного разложения несимметричных матриц с оцениваемой томностью. Автометрия, 43(2):81-96, 2007.

55. O.B. Нечаев, Э.П. Шурина. Многоссточный алгоритм решения векторным методом конечных элементов трехмерного уравнения Гельмгольца. Математическое моделирование, 17:92-102, 2005.