Решение систем линейных алгебраических уравнений является одной из фундаментальных задач математики. В частности, она возникает при решении краевых задач для дифференциальных и интегральных уравнений, к которым сводятся реальные проблемы техники, физики, экономики, математики [2] и др.
Некоторые методы решения данной задачи, такие как метод Гаусса, метод Жордана-Гаусса, метод прогонки, прямое использование формул Крамера и др., определены в терминах точных вычислений. Но использование стандартных типов данных известных языков программирования, существенно сужает множество рациональных чисел, представимых без погрешности. Таким образом, арифметические операции приходится выполнять приближенно, что часто дает неудовлетворительные результаты решения задач.
Интересно заметить, что в последнее время теория и практика решения плохо обусловленных линейных систем развивается в направлении разработки алгоритмов, устойчивых к погрешностям округления промежуточных результатов [5, 21, 22, 25, 31, 38, 46, 50, 74, 75]. Примерами таких методов являются: метод вращений, метод отражений и, др. Они содержат операции извлечения квадратного корня, вычисление синуса, косинуса и прочих иррациональных. функций, т. е. ориентированы на вычисления с приближенными числами. Методы, не ориентированные на безошибочные вычисления, как правило, не распознают случаи, когда система имеет бесконечное множество решений или не имеет их вообще, выдавая ошибочные ответы. При вычислениях с округлениями, возможно, что 1) не будет найдено ни одного подходящего решения, даже если оно имеется- 2) найдены корни при их отсутствии- 3) найдено только одно решение, при их бесконечном множестве. При безошибочных вычислениях все три случая легко идентифицировать.
Общеизвестные алгоритмы решения систем линейных алгебраических уравнений: метод Гаусса, метод Жордана-Гаусса, метод прогонки, — для преобразования данных используют только основные арифметические операции. Но на сегодняшний день нам не известно языков программирования, представляющих программисту целочисленные типы данных с более чем 64 двоичными разрядами. Однако, при использовании в указанных алгоритмах безошибочных вычислений будут исключены все возможные методические погрешности решения (так как все промежуточные операции, будут выполняться точно, без округлений), останутся только погрешности, обусловленные неточностью исходных данных.
Использование популярных программ, таких как MS Excel и MathCAD, приводит к получению неверного результата даже при решении систем линейных уравнений порядка 15. Кроме того, программы даже не выдают сообщения, что полученный результат может быть неверным [36, 37].
По-видимому, первый комплекс программ для безошибочных дробно-рациональных вычислений реализован в 1986 г. в Пермском государственном университете под руководством А.Н. Румянцева-[20, 28]. Однако факты массового использования данного комплекса программ для реальных вычислений не известны.
Развитие объектно-ориентированного программирования позволило пользователям, дополнить стандартные числовые типы, данных. Используя символьное программирование, японские программисты" К. Ш. Тан, В. Х. Стиб, Й. Харди [43] разработали класс, позволяющий выполнять операции со сверхдлинными числами. Данный класс основан на символьном программировании с использованием десятичной системы счисления. Для 32-битных операционных систем более рациональным является использование систем счисления с основанием 2 .
Указанного недостатка не имеет библиотека GMP [33]. Данная библиотека разработана под операционные системы Unix, Linux и подобные малопопулярные в нашей стране операционные системы, ее использование требует компиляции и дополнительных знаний, что затрудняет использование данной библиотеки для рядового программиста. Стоит также отметить, что для объектов GMP не предоставляется возможность их использования в параллельных вычислениях.
Целью диссертации является разработка программного обеспечения для безошибочных дробно-рациональных вычислений с использованием суперкомпьютерных технологий и его применение для решения систем линейных алгебраических уравнений. В связи с поставленной-целью решаются следующие задачи:
1. Разработка классов, обеспечивающих безошибочные дробно-рациональные и матричные вычисления.
2. Разработка параллельного программного обеспечения для безошибочного решения систем линейных алгебраических уравнений и нахождения обобщенной обратной матрицы.
3. Анализ сложности безошибочного решения систем линейных алгебраических уравнений и нахождения обобщенной* обратной: матрицы и эффективности распараллеливания.
Научная, новизна., Разработано программное обеспечение для безошибочного решения: систем линейных алгебраических уравнений, найдены битовые сложности безошибочного-решения систем различными методами:
Наиболее существенные результаты, полученные автором в результате исследования и выносимые на защиту, состоят в следующем:
1. Доказано, что при безошибочном решении систем линейных алгебраических уравнений методом Жордана-Гаусса пространственная битовая сложность не превышает o (l2), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает Ф5) соответственно, где I — число бит требуемых для представления исходных данных.
2. Доказано, что при безошибочном решении систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки пространственная битовая сложность не превышает o (lus), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает o (l3) и о (/1,5) соответственно.
— 83. Доказано, что при безошибочном нахождении обобщенной обратной матрицы Мура-Пенроуза методом Эрмита пространственная битовая сложность не превышает о (/4), а вычислительная битовая сложность при использовании алгоритма умножения столбиком* и быстрого алгоритма не превышает о (/7) и о (/5). Результаты теоретического исследования показывают возможность практического использования программы, как при анализе, так и при безошибочном решении систем линейных алгебраических уравнений.
4. Разработана библиотека классов ExactComp, в состав которой включены классы overlong, rational и matrix, расширяющие возможности безошибочных вычислений и позволяющие использовать безошибочные матричные вычисления при решении плохо обусловленных и некорректных систем линейных алгебраических уравнений в программах пользователя. Разработанные классы адаптированы для параллельных вычислений. Проведен анализ ускорения использования параллельных вычислений для решения данных задач.
Теоретическая значимость. Получены, оценки безошибочного решения систем линейных алгебраических уравнений и нахождения обобщенной обратной матрицы различными методами. Используя^ полученные оценки можно выбрать оптимальный метод, при использовании безошибочных вычислений. Также были получены оценки ускорения безошибочных вычислений при использовании суперкомпьютеров, что поможет рассчитать требуемые ресурсы для решения задач.
Практическая значимость. К вычислению обобщенной обратной матрицы сводятся реальные задачи экономики, математики, физики. Представленные в работе библиотеки (свид. РОСПАТЕНТ об официальной регистрации программы для ЭВМ № 2 009 612 777, № 990 607) позволяют реализовать безошибочное решение данной задачи.
Проведенные практические эксперименты являются подтверждением теоретических исследований, а также показывают не только возможность, но и необходимость безошибочного решения систем линейных алгебраических уравнений. Необходимость вызвана тем, что при приближенном решении конечный результат будет существенно отличаться от правильного, но это можно избежать, если выполнять все операции точно.
Методы исследования. Проведенные в работе исследования^ базируются на. методах, решения систем линейных алгебраических уравнений, методах нахождения обобщенной обратной матрицы, методах безошибочных вычислений, нахождении битовой вычислительной сложности, практических экспериментов.
Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях:
1. Международная научная конференция «Параллельные вычислительные технологии ПАВТ'2009», г. Нижний Новгород, март — апрель 2009 г.
2. Международнаянаучная конференция' «Параллельные вычислительные технологии ПАВТ'2008», г. Санкт-Петербург, январь — февраль 2008 г.
3'. Международная научная конференция «Параллельные вычислительные технологии ПАВТ'2007», г. Челябинск, январь — февраль 2007 г.'.
4. «Третья российско-германская школа по параллельным* вычислениям на высокопроизводительных системах», г. Новосибирск, август-сентябрь 2006 г.
5. «Всероссийский конкурс студенческих работ в области естественных наук», г. Москва, декабрь 2004 г.
6. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, апрель 2002 г.
7. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, февраль 2001 г.
8. Седьмая научная конференция молодых исследователей «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, февраль 2000 г.
9. Российская молодежная научная^и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, апрель 2000 г. Кроме того, результаты работы были представлены на ежегодных научно-практических конференциях Южно-Уральского государственного? университета. Работа награждена дипломами лауреата Российских научных мероприятий:
• > Диплом 1- степени по итогам 2 тура Всероссийского конкурса студенческих работ в области естественных наук, Саратов 2004 год.
• Диплом министерства промышленности, наукии технологий РФ за первый приз в номинации «Абсолютное первенство — лучшаяфабота в области естественных наук», Москва, МЕТУ им. Н. Э. Баумана, 2001 год.
• Диплом комитета общественных и межрегиональных связей! Правительства Москвы за первый приз в номинации «Лучшая работав. области Естественных наук», МГТУ им. Н. Э-Баумана,.2001 год.
Основания для? выполнения работы: Гранд губернатора! Челябинской области 2004 г.
Публикации. Основные результаты диссертации опубликованы в 14 печатных работах, получены свидетельства РосАПО об официальной регистрации программыдля ЭВМ № 990 607 «Класс rational» и № 2 009 612 777 Библиотека классов «Exact Computational».
Во введенииобоснована актуальность темы диссертационной работы, проведен обзор аналогов<�и описаны их недостатки, сформулирована цель работы, кратко охарактеризована научная новизна, возможности научного — и практического примененияотмечена связь проблемы с планами научных исследований. Кроме того, приведено краткое изложение материала работы по главам и параграфам.
В первой главе произведен обзор алгоритмов основных арифметических операций для целочисленных вычислений.
Описан класс оverlong [40], который существенно расширяет логические возможности целочисленных вычислений: диапазон пред ставимых чисел расширяется до (-(216)65536, +(216)65536). Таким образом, имеется возможность представлять целые числа, имеющие более 600 ООО десятичных разрядов.
Описан класс rational [41], который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных rational представляет собой пару. Здесь птг — целочисленная переменная типа overlong, обозначающая числитель, a dmr — целочисленная переменная типа overlong, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен 2″ 1 048 575.
Для использования классов overlong и rational достаточно подключить заголовочный файл ExactComp. h [39] в свою программу, после этого можно пользоваться объектами данных классов как объектами стандартных типов данных. Над объектами классов определены все основные арифметические операции, бинарные отношения, операторы ввода/вывода. Объем памяти, требуемый для представления объекта, зависит от значения представляемого чисI ла. Найдены битовая пространственная и вычислительная сложности сложения и умножения матриц.
Разработанный класс matrix [37], предназначен для облегчения программирования, а также улучшений визуального восприятия программ, использующих матричные вычисления. В данный класс встроены методы решения систем линейных уравнений с заданной матрицей, нахождения обратной матрицы и нахождения обобщенной обратной матрицы. Добавлена возможность использования параллельных вычислений.
Во второй главе рассмотрен метод определения гарантированной оценки погрешности решения систем линейных алгебраических уравнений, при приближенно заданных исходных данных [27, 28].
Для безошибочного вычисления, как обратной матрицы А'1, так и решения х можно использовать метод Жордана-Гаусса, а при использовании разработанного класса rational возможно исключить все методические погрешности.
Известно, что алгоритм Жордана-Гаусса имеет алгебраическую пространствен.
2 3 ную сложность 0(п) и алгебраическую вычислительную сложность 0(п). Данные оценки позволяют определить количество переменных, требуемых для решения задачи и количество арифметических операций с этими переменными. При использовании безошибочных вычислений длина переменной зависит от представляемого ей значения, следовательно, количество переменных не позволяет оценить ресурсы, необходимые для нахождения, результата. Для практического использования алгоритма требуется определить количество бит, требуемых для нахождения результата, а также количество, операций с битами.
В работе доказано, что битовая, пространственная"сложность безошибоч-* ного решения систем линейных алгебраических уравнений' методом Жордана-Гаусса не превосходит величины о (/2), а битовая вычислительная сложность не превосходит, где I — число бит, требуемых, для представления исходных данных. Также доказаночто битоваяпространственная^ сложность безошибочного решения систем линейных алгебраических уравнений, методом прогонки не превосходит величины- ^(f1'5), а битовая вычислительная-сложность не превосходит оН.
При решении практических задач бывают случаи, когда система уравнений бывает недоопределеннойили переопределенной. При решении таких некорректно поставленных задач используется понятие нормального псевдорешения. Для его нахождения можно использовать обобщенную обратную" матрицу, называемую также g-обратной.
Известно множество методов нахождения g-обратной матрицы Мура-Пенроуза. Теоретический расчет битовой сложности алгоритмови практические эксперименты показали, что наиболее оптимальным методом для вычисления обобщенной обратной матрицы является метод Эрмита. Битовая пространственная сложность вычисления обобщенной обратной матрицы Мура.
Пенроуза методом Эрмита не превосходит величины, а битовая, вычислительная сложность не превосходит.
Также в второй главе представлены результаты вычислительных экспериментов. Целью первого эксперимента испытать популярные программы MS Excel и MathCAD. Проведенный эксперимент показал, что использование этих программ, которыми, кстати, многие пользуются, может привести к получению неверного результата.
Проведенные практические эксперименты являются подтверждением теоретических исследований, а также показывают не только возможность, но и необходимость безошибочного решения систем линейных алгебраических уравнений. Необходимость вызвана тем, что при приближенном решении конечный результат будет существенно отличаться от правильного, но-это можно избежать, если выполнять все операции точно.
Многие реальные задачи имеют большую размерность п, следовательно, вычислительная и пространственная сложность этих задач будет достаточно большой, а следовательно и время, требуемое для решения будет большим. Увеличить скорость решения во многих случаях позволяет использование параллельных вычислений на нескольких компьютерах одновременно, при этом сократятся как количество операций, выполняемых на одном компьютере, так и память, требуемая для хранения промежуточных результатов.
В третьей главе предлагается адаптация разработанных классов overlong, rational и matrix к параллельным вычислениям. При организации параллельных вычислений было принято использовать MPICH, которая поддерживает стандарт MPI и имеет GNU лицензию [40].
Теоретические исследования показали, что параллельные реализации алгоритмов Эрмита и Жордана-Гаусса при решении задач с большими матрицами позволяют увеличить скорость нахождения решения в N раз, где N — число компьютеров, а которых решается задача.
Вычислительные эксперименты, проведенные в работе, подтвердил теоретически рассчитанные коэффициенты ускорения (при достаточно больших исходных данных скорость вычисления увеличится в N раз, где N — количество компьютеров, на которых решается задача). Результаты аналитического исследования и проведенного вычислительного эксперимента показывают, что использование параллельного программирования существенно уменьшает время, требуемое для безошибочного решения систем линейных уравнений.
3.5. Выводы.
Результаты аналитического исследования и проведенного вычислительного эксперимента показывают, что использование параллельного программирования существенно уменьшает время, требуемое для безошибочного решения систем линейных уравнений.
Заключение
.
1. Доказано, что при безошибочном решении систем линейных алгебраических уравнений методом Жордана-Гаусса пространственная битовая сложность не превышает o (l2), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не для представления исходных данных.
2. Доказано, что при безошибочном решении систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки пространственная битовая сложность не превышает о (/1,5), .а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает o (l3) и о (/1,5) соответственно.
3. Доказано, что при безошибочном нахождении обобщенной обратной матрицы Мура-Пенроуза методом Эрмита пространственная битовая сложность не превышает о (/4), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает о (?) и o{l5).Результаты теоретического исследования показывают возможность практического использования программы, как при анализе, так и при безошибочном решении систем линейных алгебраических уравнений.
4. Проведены практические эксперименты, подтверждающие теоретические исследования, а также показывающие не только возможность, но и необходимость безошибочного решения систем линейных алгебраических уравнений.
5. Разработана библиотека классов ExactComp, в состав которой включены классы overlong, rational и matrix, расширяющие возможности безошибочных вычислений и позволяющие использовать безошибочные матсоответственно, где I — число бит требуемых ричные вычисления при решении плохо обусловленных и некорректных систем линейных алгебраических уравнений в программах пользователя. Диапазон чисел, представляемых объектами класса overlong расширен до (-21 048 575, 21 048 575), а минимальный шаг дискретизации чисел, представляемых объектами класса rational может достигать (2″ 1 048 575). 6. Разработанные классы адаптированы для параллельных вычислений. Проведен анализ ускорения использования параллельных вычислений для решения данных задач.
