автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Комплекс программ для безошибочных дробно-рациональных вычислений и его применение для решения систем линейных алгебраических уравнений

09-5 2350

На правах рукописи

Германенко Максим Игоревич

КОМПЛ ЕКС ПРОГРАММ ДЛЯ БЕЗОШИБОЧНЫХ ДРОБНО-РАЦИОНАЛЬНЫХ ВЫЧИСЛЕНИЙ И ЕГО ПРИМЕНЕНИЕ ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Челябинск - 2009

Работа выполнена на кафедре экономико-математических методов и статистики Южно-Уральского государственного университета.

Научный руководитель - доктор физико-математических наук,

профессор Пашоков Анатолий Васильевич.

Официальные оппоненты: доктор физико-математических наук,

профессор Кипнис Михаил Маркович;

доктор физико-математических наук, профессор Сурнев Виктор Борисович.

Ведущая организация -

Институт математики и механики УрО РАН.

Защита диссертации состоится 18 ноября 2009 г., в 12 часов, на заседании диссертационного совета Д 212.298.14 при Южно-Уральском государственном университете по адресу. 454080, г Челябинск, пр. им. В.И. Ленина, 76.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

Автореферат разослан 25 сентября 2009 г.

Ученый секретарь диссертационного совета

Р сз с, с и н с к л я г а г. у д а р г. т п им л я

Б И Б Л » О 1 Ь К А 2 о а 9

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

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

Некоторые методы решения данной задачи, такие как метод Гаусса, метод Жордана-Гаусса, метод прогонки, прямое использование формул Крамера и др., определены в терминах точных вычислений. Но использование стандартных типов данных известных языков программирования, существенно сужает множество рациональных чисел, представимых без погрешности. Таким образом, арифметические операции приходится выполнять приближенно, что часто дает неудовлетворительные результаты решения задач.

Интересно заметить, что в последнее время теория и практика решения плохо обусловленных линейных систем развивается в направлении разработки алгоритмов, устойчивых к погрешностям округления промежуточных результатов. Примерами таких методов являются: метод вращений, метод отражений и др. Они содержат операции извлечения квадратного корня, вычисление синуса, косинуса и прочих иррациональных функций, т.е. ориентированы на вычисления с приближенными числами. Методы, не ориентированные на безошибочные вычисления, как правило, не распознают случаи, когда система имеет бесконечное множество решений или не имеет их вообще, выдавая ошибочные ответы. При вычислениях с округлениями, возможно, что 1) не будет найдено ни одного подходящего решения, даже если оно имеется; 2) найдены корни при их отсутствии; 3) найдено только одно решение, при их бесконечном множестве. При безошибочных вычислениях все три случая легко идентифицировать.

Общеизвестные алгоритмы решения систем линейных алгебраических уравнений: метод Гаусса, метод Жордана-Гаусса, метод прогонки, - для преобразования данных используют только основные арифметические операции. Но на сегодняшний день нам не известно языков программирования, представляющих программисту целочисленные типы данных с более чем 64 двоичными разрядами. Однако, при использовании в указанных алгоритмах безошибочных вычислений будут исключены все возможные методические погрешности решения (так как все промежуточные операции будут выполняться точно, без округлений), останутся только погрешности, обусловленные неточностью исходных данных.

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

Развитие объектно-ориентированного программирования позволило пользователям дополнить стандартные числовые типы данных, Используя символьное программирование, японские программисты К.Ш.Тан, В.Х.Стиб, Й.Харди разработали класс, позволяющий выполнять операции со сверхдлинными числами. Данный класс основан на символьном программировании с использованием десятичной системы счисления. Для 32-битных операционных систем более рациональным является использование систем счисления с основанием 216.

Указанного недостатка не имеет библиотека GMP. Данная библиотека разработана иод операционные системы Unix, Linux и подобные малопопулярные в нашей стране операционные системы, ее использование требует компиляции и дополнительных знаний, что затрудняет использование данной библиотеки для рядового программиста. Стоит также отметить, что для объектов GMP не предоставляется возможность их использования в параллельных вычислениях.

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

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

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

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

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

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

1. Доказано, что при безошибочном решении систем линейных алгебраических уравнений методом Жордана-Гаусса пространственная битовая сложность не превышает о(/2), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает о(/3,5) и О(Р) соответственно, где I - число бит требуемых для представления исходных данных.

2. Доказано, что при безошибочном решении систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки пространственная битовая сложность не превышает о(/1,5), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает о(/') и о(/1,5) соответственно.

3. Доказано, что при безошибочном нахождении обобщенной обратной матрицы Мура-Пенроуза методом Эрмита пространственная битовая сложность не превышает о(/4), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает Результаты теоретического исследования показывают возможность практического использования программы, как при анализе, так и при безошибочном решении систем линейных алгебраических уравнений.

4. Разработана библиотека классов ExactComp, в состав которой включены классы overlong, rational и matrix, расширяющие возможности безошибочных вычислений и позволяющие использовать безошибочные матричные вычисления при решении плохо обусловленных и некорректных систем линейных алгебраических уравнений в программах пользователя. Разработанные классы адап-

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

Практическая значимость. К вычислению обобщенной обратной матрицы сводятся реальные задачи экономики, математики, физики. Представленные в работе библиотеки (свид. РОСПАТЕНТ об официальной регистрации программы для ЭВМ №2009612777, №990607) позволяют реализовать безошибочное решение данной задачи.

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

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях:

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 год.

Публикации. Основные результаты диссертации опубликованы в 15 научных работах, в том числе 2 публикации их списка ВАК, также получены 2 свидетельства РОСПАТЕНТ об официальной регистрации программы.

В работах [2-8] научному руководителю принадлежит постановка задачи и обсуждение результатов.

В работе [31 описание класса rational, написание ряда алгоритмов класса принадлежит автору диссертации.

В работах [4, 5] доработка для параллельных вычислений классов overlong и rational, написание класса matrix и программы алгоритмов решения линейных систем осуществлено автором диссертации.

Объем работы. Диссертационная работа состоит из введения, трех глав, списка используемой литературы и 4-х приложений; изложена на 131 страницах машинописного текста, содержит 35 рисунков и 7 таблиц, библиография содержит 77 наименований. В приложения сведения о внедрении работы и фрагменты исходных текстов программ.

Содержание работы

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

В первой главе произведен обзор алгоритмов основных арифметических операций для целочисленных вычислений. Описан класс overlong, который существенно расширяет логические возможности целочисленных вычислений: диапазон представимых чисел расширяется до (-(2|6)65ИЙ, +(216)65536). Таким образом, имеется возможность представлять целые числа, имеющие более 600 000 десятичных разрядов. Ранее доказано, что битовая пространственная сложность результата арифметической операции °е {+,—,/,х} над рациональными числами р, q не превосходит величины L(po q)< L(p)+L(q). Проведенный анализ битовой вычислительной сложности, при выполнении алгоритма столбиком, показал что имеет место следующее неравенство С{р° q)< L{p)-b{q\ При использовании быстрого алгоритма умножения вычислительная сложность операций с дробно-рациональными числами не будет превосходить значения

0{{L{p)+L{q))\ogl{L{p)+L{q))\ Описан класс rational, который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных rational представляет собой пару <nmr, dm». Здесь птг - целочисленная переменная тина overlong, обозначающая числитель, a dmr - целочисленная переменная типа over-

long, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен 2~1(М8575.

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

Для использования классов overlong и rational достаточно подключить заголовочный файл ExactComp.h в свою программу, после этого можно пользоваться объектами данных классов как объектами стандартных типов данных. Над объектами классов определены все основные арифметические операции, бинарные отношения, операторы ввода/вывода. Объем памяти, требуемый для представления объекта, зависит от значения представляемого числа.

В работе показано, что битовая пространственная и вычислительная сложности сложения п х-т матрицы А и В не превосходят величин

L(A + в) < L{a)+L(b), С{а + В) < пт{мл + Ма)

соответственно, а битовая пространственная и вычислительная сложности умножения п х;н матрица А и т */ матрица В не превосходят величин L(A ■ В) < mnl{MA +МВ), С(А ■ В) < о{птг1С. {А, В)) соответственно, где С. - битовая вычислительная сложность выбранного метода умножения. Здесь МА - число бит требуемых для представления матрицы А.

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

Во второй главе рассмотрен метод решения систем линейных алгебраических уравнений с гарантированной оценкой погрешности при приближенно заданных исходных данных. Известно, что система Ах = Ъ с приближенно заданной матрицей имеет единственное решение, если

и.н 1

где ||Д|| - норма матрицы погрешностей, а ¡Л~'|| - норма обратной матрицы системы. Если система имеет единственное решение, тогда имеет место оценка

1М!

Для безошибочного вычисления, как обратной матрицы А ', так и решения .г можно использовать метод Жордана-Гаусса, а при использовании разработанного класса гаНопа! возможно исключить все методические погрешности. Известно, что алгоритм Жордана-Гаусса имеет алгебраическую пространственную сложность 0(пг) и алгебраическую вычислительную сложность 0{п ). Данные оценки позволяют определить количество переменных, требуемых для решения задачи и количество арифметических операций с этими переменными. При использовании безошибочных вычислений длина переменной зависит от представляемого ей значения, следовательно, количество переменных не позволяет оценить ресурсы, необходимые для нахождения результата. Для практического использования алгоритма

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

Лемма 1. Пусть А = (atf) - невырожденная целочисленная матрица пхп, т= шах L{a ). Тогда

¿(det А) < n(log2 п + т).

Лемма 2. Пусть А = (а,у) - невырожденная пхп рациональна матрица, m = тах^яД Тогда

L(det А) < n(log2 п + (2 л + l)m).

Теорема 1. Пусть - система линейных алгебраических уравнений, А - невырожденная матрица пхп с рагцюнальными элементами, Ь - n-мерный вектор с рациональными элементами,

m = max] max L(a,:), max L(h,)(

" (=1,2,...л ''

тогда

п

L(x) = £ L(x-) <2л2 (log2 n + (In + l)m).

i=i

Теорема 2. Пусть даны невырожденная п хп система уравнений Ах = Ь с ра-циональньши коэффициентами, являющаяся приближением некоторой пхп системы уравнений Ах = b ; матрицы абсолютных погрешностей: ={Sij):(Vi,j = l,2,...,n)öiJ <|a(J.-Su\,

^b = (<5j): (у/ = 1,2,...,n) 8J < -¿yj ;

а также верхняя оценка числа бит, требуемых для одного элемента исходных данных

т = шах j max jL^),L(Sy)}, max {ЦЬ,),

Тогда, для нахождения как решения х, так и гарантированной нормы погрешности |Ar|j = х\потребуется не более 0(п4т) бит памяти и не более 0(п7т2) битовых onepaifuü.

Пусть / - число бит, требуемых для представления исходных данных. При ограниченном m будем иметь I = @(п2т). Из теоремы [2] следует, что в этом случае зависимость битовой пространственной сложности от величины I не превосходит величины О (j2\ а зависимость битовой вычислительной сложности (при использовании быстрых алгоритмов умножения) от величины / не превосходит 0(/2,5).

Численные методы решения краевых задач для линейных дифференциальных и интегральных уравнений сводятся к решению систем линейных алгебраических уравнений с (2к+1)-диагоиалыюй матрицей. Для решения таких систем используется метод прогоики. С одной стороны, данный метод имеет низкую алгебраическую вычислительную сложность (т. е. количество операций с числами) равна О(п), где п - порядок системы. С другой стороны он не позволяет решать плохо обусловленные системы. Для устранения последнего можно использовать безошибочные

вычисления. Однако, при безошибочных вычислениях, как и в случае алгоритма Жордана-Гаусса, адекватной оценкой сложности будет не алгебраическая, а битовая вычислительная сложность (т. е. количество операций с битами).

Теорема 3. Пусть даны невырожденная система уравнений Ах = Ь, А - трех-диагонапьная п*п матрица с рациональными коэффициентами, Ь - п*к матрица свободных членов, пусть также дана верхняя оценка числа бит, требуемых для одного элемента исходных данных

Тогда, для нахождения решения потребуется не более 0(ктп3) бит памяти и не более 0(ктп3) операций с ними.

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

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

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

Теорема 4. Пусть ЦА,„*П) длина исходной матрицы. Тогда, для нахождения обобщенной обратной матрицы Мура-Пенруоза алгоритмом Эрмита потребуется не болееО(11,5) бит памяти и не болееО(1) операгцш с ними.

Также во второй главе были проведены практические эксперименты. Эксперимент состоял в решении системы Их - Не, где

Очевидно, что в этом случае х должен быть единичным вектором. Результаты, полученные при /1=15, с использованием популярных коммерческих программ MS Excel и MathCAD, приведены на рис. 1.

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

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

MS Excel (/1=15)__MathCAD (""15)

1.95 0.99

72.01 1.04

-717.44 0.96

2648.23 0 59

-4625.26 1.47

4207.05 4.28

-1710.44 -3.74

524.03 х— -¡4.85

-996.25 56.99

974.50 ^ -78.42

-439.50 69.18

106.75 -40.54

-12.63 20.19

0.84 -5.05

1.16 1.91

Рис. 1. Результаты эксперимента использования программ MS Excel и MathCAD

Матрица H, известная как матрица Гильберта, является плохообуслоилснной. Подобные системы, с использованием приближенных вычислении, не удается решить уже при п > 5. Были решены все системы линейных уравнений, для п = 3, ..., 250. Расчеты осуществлялись по методу Жордана-Гаусса, методу Гаусса и методу прогонки. При решении системы методом прогонки также использовалась матрица Гипьберта с ненулевыми элементами только на трех главных диагоналях. Результаты вычислительных экспериментов приведены рис. 2 и рис. 3.

Рис. 2. Время (секунды) решения рцс. 3. Память (число слов памяти),

системы методами Гаусса, Жордана- требуемая для решения системы Гаусса и методом прогонки

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

В третьей главе предлагается адаптация разработанных классов overlong, rational и matrix к параллельным вычислениям. При организации параллельных вычислений было принято использовать MPICH, которая поддерживает стандарт MPI и имеет GNU лицензию.

Передача класса rational между узлами внутренними средствами MPI невозможна, так как данный класс содержит два объекта класса overlong, которые в свою очередь содержат длину массива и указатель на массив содержащий число. Поэтому объявить структуру rational по стандарту MPI не возможно по двум причинам:

• необходимо хранить указатель;

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

Из вышесказанного следует, что стандартными средствами передачу типа rational осуществить не удастся. Очевидными решениями будет упаковка rational в буфер с целыо дальнейшей передачи. Данный вариант позволяет обойтись одной транзакцией, и поэтому взят за основу модификации. Для передачи типов overlong, rational были переопределены стандартные методы передачи данных в среде MPI.

С целыо целостности изложения, рассмотрим предварительно используемый для распараллеливания последовательный алгоритм. Фрагменты листинга его про-

граммной реализации приведены на рис. 4. Система хранится в матрице т, включая столбец свободных членов._ _ _

«define N 500 int SolveQ (

#include <stdio.h> rational zero;

/¿Include <iostream> Int i,],k;

((Include "rational.h" //Инициализация rowN

using namespace std; for (¡=0; kN; i++) rowN[i]=i; for (1=0; i<N; i++){

rational m[N][N+1]; ]=i;

Int rowN[N]; //Поиск ведущее строки while((m[rowN[]]][l] ==zero)

void SubLine(int i, Int j) ( &&(|<N)))++;

rational R,z; if (|=N) break;

R=m[rowN[i]l[|]; // Определитель 0

for(int k=j; k < N+1; k++) ( if(l!=i)Swap(i,l);

z=R*m[rowN[j]][k];

m[rowN[i]][k]-=z; } ) //Ведущее преобразование DivLine(i); for (k=0; k<i; k++) SubLine(k, 1);

void DivLinefint I) { for (k=i+1; k<N; k++) SubLine(k, i);

rational R; }

R=m(rowN[i])[i]; return QI=N);

for(lnt l=i ;I<N+1; I++) }

m[rowN[i]][l]/=R; ) Int main(){ ReadFile();

void Swapfint i, Int j){ if (Solve()) WriteResull();

k=rowN[l]; rowN[i]= rowN[j]; else cout«"Det=0\n";

rowN[il=k; } return 0; }

Рис, 4. Алгоритм решения систем уравнений методом Жордана-Гаусса

Для строк матрицы вводятся состояния: открытая, закрытая и ведущая. Открытыми строками будем называть строки с номером j, у которых на /-м шаге выполнения алгоритма модифицированный номер го\\'МЦ]>1. Первый цикл в теле функции 5о/уе() выполняет присваивания что соответствует присваива-

нию всем строкам статуса открытая. Число выполнений тела второго цикла равно числу переменных. При /'-м выполнении тела цикла из открытых строк по выбирается строка у, имеющая ненулевой элемент в столбце ;'. Найденной строке присваивается статус ведущая, при необходимости производится модификация значений го-мЫ\]] и гои'/ф']. Далее с помощью процедуры ОЫЫпе{) производится нормировка ведущей строки, а с помощью процедуры БиЬЫпеО осуществляется ведущее преобразование других строк матрицы, состоящее в обнулении элементов /-го столбца, не принадлежащих ведущей строке. После этого ведущая строка переводится в состояние закрытой.

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

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

Внешний цикл функции &>Л>е() выполняется для каждой переменной системы уравнений. При /-м выполнении тела цикла в каждом процессе из открытых строк выбирается строка_/', имеющая максимальный по абсолютной величине элемент в столбце / локального фрагмента матрицы системы. Затем определяется ведущий процесс, в котором находится максимальный по модулю элемент столбца /. Если модуль найденного элемента равен 0, то выполнение программы прекращается с выводом сообщения "0ег=0". В противном случае строке у ведущего процесса присваивается статус «ведущая» и устанавливается модифицированное значение гоыЫ\}} = /.

Далее в ведущем процессе производится нормировка ведущей строки и ее рассылку остальным процессам. Функция БиЬЫпеО осуществляется ведущее преобразование строк матрицы, состоящее в обнулении элементов /'-го столбца, не принадлежащих ведущей строке. После этого ведущая строка переводится в состояние закрытой.

Если исходными данными является п*п матрица, т - количество бит, требуемых для представления одного элемента исходной матрицы, и задача решается на N компьютерах, то ускорение параллельной реализации алгоритма Жордана-Гаусса при использовании параллельный вычислений составит:

Вычислительный эксперимент проводился на кластере кафедры ЭММиС ЮУрГУ. Данный кластер состоит из основного и восьми вспомогательных узлов,

N

объединенных в локальную сеть посредством коммутатора Allied Telesyn АТ-FS716E 100Base-TX.

Примерная расчетная пиковая производительность кластера в соответствии с данными, взятыми с сайта производителя, составляет величину ПРПГОС=8*2,4*2+2*2,8*2 = 49,6 Gflops.

IIa узлах кластера присутствуют только средства необходимые для функционирования среды MPI, I Ia основном узле установлены оконные менеджеры XFCE4 и GNOME, а также другие пакеты необходимые для написания, отладки и запуска программ.

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

алгебраических уравнений Ах = Ь, где ^ = D /(' + J + l)]"j=o - матрица Гильберта, ^ = ['1=о. Результаты вычислительного эксперимента приведены на рис. 5.

10000,000 т~

1000,000

10,000

1,000

JL.

I

|| □ 1 процессор I 02 процессора i □ 4 процессора 6 процессоров 6 процессоров |i □ 10 процессоров

40 80 120 160 200 240 число уравнений

Рис. 5. Время решения систем уравнений на разных количествах процессоров

Известны реализации параллельных алгоритмов умножения матриц и метода Жордана-Гаусса. Используя разработанные классы overlong и rational в этих реализациях можно выполнять все операции точно, не задумываясь о длине передаваемых операндов. Метод Эрмита использует умножение матриц и диагональную редукцию, которая выполняется методом Жордана-Гаусса. Следовательно, не составит труда написать его программную реализацию. Для параллельной реализации метода Жордана-Гаусса в класс matrix были добавлены возможности параллельных вычислений. Таким образом при использовании классов overlong, rational и matrix последовательные программы практически не будут отличатся параллельных.

Если исходными данными является й|Хк2 матрица, т - количество бит, требуемых для представления одного элемента исходной матрицы, тогда коэффициент ускорения параллельной реализации метода Эрмита, выполняемого на N компьютерах не будет превышать ускорения на участке с наибольшей вычислительной сложностью:

_N_

j ^ CN I ^процессора J

"'"'i, J

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

В заключении подведены итоги проведенного исследования.

1. Создана библиотека ExactComp, позволяющая использовать безошибочное выполнение основных арифмегических операций над полем рациональных чисел и матричные вычисления использовать в программах пользователя. Данная библиотека состоит из классов overlong, rational и matrix. Диапазон чисел, представляемых объектами класса overlong расширен до (-21048575, 21048575), а минимальный шаг дискретизации чисел, представляемых объектами класса rational может достигать (2 1 ). Помимо матричных операций в класс matrix добавлены возможности: решение систем уравнений с заданной матрицей, обращение матрицы, нахождение обобщенной обратной матрицы и использование параллельных вычислений.

2. Проведен анализ, который показал, что при безошибочном решении систем линейных алгебраических уравнений методом Жордана-Гаусса пространственная битовая сложность не превышает о(/2), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает Of/3'5) и o(lxs) соответственно, где I - число бит требуемых для представления исходных данных. При безошибочном решении систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки пространственная битовая сложность не превышает о(/'5), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает не превышает о(/') и о(/и) соответственно. При безошибочном нахождении обобщенной обратной матрицы Мура-Пенроуза методом Эрмита пространственная битовая сложность не превышает о(/4), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает о{С). Результаты теоретического исследования показывают возможность практического использования программы, как при анализе, так и при безошибочном решении систем линейных алгебраических уравнений. Проведены практические эксперименты, подтверждающие теоретические исследования, а также показывающие не только возможность, но и необходимость безошибочного решения систем линейных алгебраических уравнений.

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

Публикации автора по теме диссертации

В журналах, рекомендованных ВАК РФ

1. Программное обеспечение безошибочных дробно-рациональных вычислений и его применение для решения линейных систем / М.И. Германенко // Вестник Нижегородского университета им. Н. И. Лобачевского. Серия: «Математика и информационные технологии». - 2009. - № 4. - С. 172-180.

2. Безошибочное решение систем линейных алгебраических уравнений / А.В. Панюков, М.И. Германенко // Вестник Южно-Уральского государственного университета. Серия: «Математика, физика, химия» - 2009. - Вып. 12. - №10 (143). - С. 28-35.

В других изданиях

3. Свидетельство РОСПАТЕНТ № 990607 «Класс rational» / А.В. Паиюков, М.М. Силаев, М.И. Германенко. - 1999.

4. Распараллеливание алгоритмов решения систем линейных алгебраических уравнений с применением вычислений без округлений / А.В. Панюков, М.И. Германенко, В.В. Горбик // Параллельные вычислительные технологии (ПаВТ'2007): Труды международной научной конференции (г. Челябинск, 29 января - 2 февраля 2007 г.). - Том 2. - С. 238-249.

5. Свидетельство РОСПАТЕНТ № 2009612777. Библиотека классов «Exact Computational» / А.В. Пашоков, М.И. Германенко, В.В. Горбик. - 2009.

6. Параллельные алгоритмы безошибочного вычисления матрицы Мура-Пенроуза / А.В. Паиюков, М.И. Германенко // Параллельные вычислительные технологии (ПаВТ'2008): Труды международной научной конференции (Санкт-Петербург, 28 января - 1 февраля 2008 г.). - С. 215-223.

7. Оценка сложности безошибочного решения систем линейных алгебраических уравнений с использованием класса RATIONAL / А.В. Панюков, М.И. Германенко // Вычислительные технологии - 2000 - Новосибирск: Институт вычислительных технологий СО РАН. URL: http://www.nsc.ro/ws/ct-2000/125.

8. Сложность нахождения гарантированной оценки решения приближенно заданной системы линейных алгебраических уравнений / А.В. Панюков, М.И. Германенко И Известия Челябинского научного центра. - 2000. - 4(9). - С. 11-15. URL: http://www.sci.urc.ac.ru/news/2000 3.

9. Оценка сложности решения систем линейных алгебраических уравнений с использованием класса Rational / М.И. Германенко // Научные труды молодых исследователей программы «Шаг в будущее».-М.: I-ITA «АПФН». - 2000 г. -Том 3, - С. 90-98.

10. Нахождение гарантированных оценок решения приближенно заданной системы линейных алгебраических уравнений / М.И. Германенко // Научные труды молодых исследователей программы «Шаг в будущее» - М.: НТА «АПФН». -2001 г.-Том4.-С. 170-178.

11. Аналитическое и экспериментальное исследование сложности безошибочного решения систем линейных алгебраических уравнений / М.И. Германенко // Тезисы второго Международного конгресса студентов, молодых ученых и специалистов «Молодежь и наука - третье тысячелетие» / YSTM'02 (Москва, 15 -19 апреля 2002 г.) - М.: IITA «АПФН». - 2002 г. - Часть 2. - С. 11-12.

12. Программное обеспечение безошибочных дробно-рациональных вычислений и его применение для решения линейных систем / М.И. Германенко // «Всероссийский конкурс на лучшие научные работы студентов по естественным, техническим (проекты в области высоких технологий) и инновационным научно-образовательным проектам». Материалы итоговой конференции - М.: МИЭМ. -2004г.-С. 328-331.

13. Программное обеспечение безошибочных дробно-рациональиых вычислений и его применение для решения линейных систем / М.И. Германенко // Всероссийский конкурс на лучшие научные работы по техническим наукам (проекты в области высоких технологий): Тезисы проектов - М.: МИЭМ. - 2004 г. -Том 2.-С.451-456.

14. Программное обеспечение безошибочных дробно-рациональных вычислений и его применение для решения линейных систем / М.И. Германенко // Всероссийский конкурс среди учащейся молодежи высших учебных заведений Российской Федерации на лучшие научные работы студентов по естественным наукам: Тезисы научных работ. Саратов: Сарат. гос. техн. ун-т. - 2004 г. -С. 28-30.

15. Использование параллельных и распределенных вычислений для безошибочных дробно-рациональных вычислений / М.И. Германенко // Новосибирск: Институт вычислительных технологий СО РАН. - 2006. URL: http://www.nsc.ru/ws/show abstract.dhtml?ru+152+10461.

16. Приложение для безошибочного нахождения обобщенной обратной матрицы методом Мура-Пенроуза и Безошибочное решение систем линейных алгебраических уравнений / М.И. Германенко // Информационные технологии моделирования и управления. - 2009. - №1 (53). - С. 78-87.

17. Программное обеспечение безошибочных дробно-рациональных вычислений и его применение для решения линейных систем / М.И. Германенко // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Новгород, 30 марта - 3 апреля 2009 г.). - С. 147156.

Работа выполнена при поддержке

гранта губернатора Челябинской области 2004 г., гранта РФФИ, №07-01-96035-р_урал_а.

Германенко Максим Игоревич

КОМПЛЕКС ПРОГРАММ ДЛЯ БЕЗОШИБОЧНЫХ ДРОБНО-РАЦИОНАЛЬНЫХ ВЫЧИСЛЕНИЙ И ЕГО ПРИМЕНЕНИЕ ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Издательский центр Южно-Уральского государственного университета

Подписано в печать 07.09.2009. Формат 60x84 1/16. Печать цифровая. Усл. печ. л. 0,93. Уч.-изд. л. 1. Тираж 110 экз. Заказ 365/403.

Отпечатано в типографии Издательского центра ЮУрГУ. 454080, г. Челябинск, пр. им. В.И. Ленина, 76.

2008131939

2008151939

ВВЕДЕНИЕ.

1. АЛГОРИТМЫ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ БЕЗОШИБОЧНЫХ ДРОБНО РАЦИОНАЛЬНЫХ ОПЕРАЦИЙ.

1.1. Целочисленные вычисления.

1.1.1. Сложение неотрицательных чисел.'.

1.1.2. Вычитание неотрицательных чисел.

1.1.3. Сложение и вычитание целых чисел.

1.1.4. Умножение целых чисел.

1.1.5. Деление и остаток от деления целых чисел.

1.1.6. Наибольший общий делитель.

1.1.7. Класс overlong.

1.1.8. Выводы и результаты.

1.2. Дробно-рациональные вычисления.

1.2.1. Оценка вычислительной и пространственной сложностей арифметических операций с рациональными числами.

1.2.2. Класс rational.

1.2.3. Арифметические операции с дробно-рациональными числами.

1.2.4. Выводы и результаты.

1.3. Матричные вычисления.

1.3.1. Оценка вычислительной и пространственной сложностей арифметических операций с матрицами.

1.4. Выводы.

-32. ПРИМЕНЕНИЕ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ ДЛЯ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ.

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

2.2. Использование метода Жордана-Гаусса.

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

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

2.3. Безошибочное решение систем с трехдиагональными матрицам

2.3.1. Метод прогонки.

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

2.4. Недоопределенные и переопределенные системы. Обобщенная обратная матрица.

2.4.1. Обобщенная обратная матрица.

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

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

Практическая значимость. К вычислению обобщенной обратной матрицы сводятся реальные задачи экономики, математики, физики. Представленные в работе библиотеки (свид. РОСПАТЕНТ об официальной регистрации программы для ЭВМ № 2009612777, № 990607) позволяют реализовать безошибочное решение данной задачи.

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

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях:

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 печатных работах, получены свидетельства РосАПО об официальной регистрации программы- для ЭВМ № 990607 «Класс rational» и № 2009612777 Библиотека классов «Exact Computational».

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

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

Описан класс оverlong [40], который существенно расширяет логические возможности целочисленных вычислений: диапазон пред ставимых чисел расширяется до (-(216)65536, +(216)65536). Таким образом, имеется возможность представлять целые числа, имеющие более 600 ООО десятичных разрядов.

Описан класс rational [41], который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных rational представляет собой пару <nmr, dmr>. Здесь птг - целочисленная переменная типа overlong, обозначающая числитель, a dmr - целочисленная переменная типа overlong, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен 2"1048575.

Для использования классов 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 расширен до (-21048575, 21048575), а минимальный шаг дискретизации чисел, представляемых объектами класса rational может достигать (2"1048575). 6. Разработанные классы адаптированы для параллельных вычислений. Проведен анализ ускорения использования параллельных вычислений для решения данных задач.

1. Азбелев, Н. В. Введение в теорию функционально-диференциальных уравнений / Н. В. Азбелев, В. П. Максимов, J1. Ф. Рахматуллина // М.: Наука. - 1991.

2. Акушский, Н.Я. Машинная арифметика в остаточных классах / Н.Я. Акушский, Д.И. Юдицкий // М. «Сов. радио». 1968. - 439 с.

3. Богачев, К. Ю. Основы параллельного программирования / К. Ю. Бо-гачев // М., БИНОМ, Лаборатория знаний. 2003.

4. Вержбицкий, В. М. Численные методы (линейная алгебра и нелинейные уравнения): Учеб. Пособие для вузов / В. М. Вержбицкий // М.: Высш. шк. 2000. - 266 е.: ил.

5. Воеводин, В. В. Ошибки округлений и устойчивость в прямых методах линейной алгебры / В. В. Воеводин // М.: Наука. 1969.

6. Воеводин, В. В. Вычислительные основы линейной алгебры / В. В. Воеводин // М.: Наука. 1977.

7. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин // С.-Петербург: «БХВ-Петербург». 2002.

8. Воеводин, Вл. В. Решение больших задач в распределенных вычислительных средах / Вл. В. Воеводин // Автоматика и телемеханика. -2007. № 5. - С. 32-45.

9. Гашков, С. Б. Арифметика. Алгоритмы. Сложность вычислений / С. Б. Гашков, В. Н. Чубариков // Учеб. Пособие для вузов/Под ред. В.А. Садовничего 2-е изд., перераб. - М.: Высш. шк. - 2000. - 320 с.

10. Германенко, М. И. Использование параллельных и распределенных вычислений для безошибочных дробно-рациональных вычислений / М. И. Германенко // Конференции ИВЦ СО РАН (http://www.nsc.rn/ws/show abstract.dhtml?ru+l52+10461).

11. Годунов, С. К. Решение систем линейных алгебраических уравнений / С. К. Годунов Новосибирск: Наука. - 1980.

12. Годунов, С. К. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах / С. К. Годунов, А. Г. Антонов, О. П. Кирилюк Новосибирск: Наука. - 1992.

13. Грегори, Р., Безошибочные вычисления. Методы и приложения / Р. Грегори, Е. Кришнамурти, пер. с англ. М.: Мир. - 1988. - 208 с.

14. Икрамов, X. Д. Численные методы линейной алгебры / X. Д. Икра-мов М.: Знание. - 1987. (Новое в жизни, науке, технике. Сер. «Математика, кибернетика». - №4).

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

16. Ильин, В. П. Методы и технологии конечных элементов / В. П. Ильин // Новосибирск: Изд. ИВМиМГ СО РАН. 2007.

17. Ильин, В. П. Параллельные алгоритмы для больших прикладных задач: проблемы и технологии / В. П. Ильин // Автометрия, т.43. -2007.-№2. -с. 3-21.

18. Ильин, В. П. Параллельные алгоритмы решения разделяющихся краевых задач / В. П. Ильин, Д. В. Кныш // Санкт-Петербург, изд. Политехи, ун-та (СПбПГУ). 2008. - с. 107-118.

19. Ильин, В. П. Трехдиагональные матрицы и их приложения / В. П. Ильин, Ю. И. Кузнецов // М.: Наука. 1985.

20. Кнут, Д. Искусство программирования для ЭВМ. т.2. Получисленные алгоритмы / Д. Кнут, пер. с англ. М.: Мир. - 1977. - 724 с.

21. Люстерник, Л. А. Элементы функционального анализа / Л. А. Люс-терник, В. И. Соболев М. Наука. - 1965.

22. Максимов, В. П. Арифметика рациональных чисел и компьютерное исследование интегральных уравнений / В. П. Максимов // Соросов-ский образовательный журнал. 1999. - №3.

23. Максимов, В. П. Краевые задачи и задачи импульсного управления в экономической динамике / В. П. Максимов, А. Н. Румянцев // Изв. вузов. Математика. 1993. - №5. - С. 56-71.

24. Малышкин, В.Э. Параллельное программирование мультикомпью-теров / В. Э.Малышкин, В. Д.Корнеев // Новосибирск, изд.НГТУ. -2006.

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

26. Михлин, С. Г. Лекции по линейным интегральным уравнениям / С. Г. Михлин // М.: Физматгиз. 1959.

27. Официальный сайт библиотеки GMP (http://www.gmplib.com).

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

29. Свидетельство РОСАТЕНТ № 2009612777, Библиотека классов «Exact Computational» / А. В. Панюков, М. И. Германенко, В.В. Горбик.

30. Свидетельство РОСПАТЕНТ № 990486, «Класс overlong» / А. В. Панюков, М. М. Силаев.

31. Свидетельство РОСПАТЕНТ № 990607, «Класс rational» / А. В. Панюков, М. М. Силаев, М. И. Германенко.

32. Страуструп, С. Б. Язык программирования С++ / С. Б. Страуструп // М.: Радио и связь. 1991. - 349 с.

33. Тан, К. Ш. Символьный С++: Введение в компьютерную алгебру с использованием объектно-ориентрованного программирования / К. Ш. Тан, В.-X. Стиб, Й. Харди//М.: Мир. 2001. - 662 с.

34. Шпаковский, Г.И., Программирование для многопроцессорных систем в стандарте MPI / Г. И. Шпаковский, Н. В. Серикова // Минск: БГУ. 2002.

35. Aho, A. The Design and Analysis of Computers Algorithms / A. Aho, J. Hopcroft, and J. Ullman // Addison-Wesley. 1974.

36. Bailey, D. H. FFT's in external or hierarchical memory / D. H. Bailey // Journal of Supercomputing. 1990. - 4.

37. Bailey, D.H. Multiprecision translation and execution of Fortran programs / D.H. Bailey // ACM Transactions on Mathematical Software.1993. 19(3).

38. Benzi, M. Numerical solution of sadde point problems / M. Benzi, G. Go-lub, J. Leisen // Acta Numer. v. 14. - 2005. - pp. 1-137.

39. Carriero, N. "How to write parallel programs A guide to the perplexed" / N. Carriero, D. Gelernter // Сотр. Sci. Tech Report No. DCSRR-628, Yale University. - 1988.

40. Collins, G. E. Improved techniques in univariate polynomial factorization / G. E. Collins, M. J. Encarnacion // In preparation. 1994.

41. Encarnacion, M. J. On a modular algorithm for computing gcds of polynomials over algebraic number fields / M. J. Encarnacion // ACM Press.1994. pp. 58-62.

42. Gathen, J. "Parallel algorithms for algebraic problems" / J. Gathen // SIAM J. Сотр. pp. 802-824. - 1984.

43. Higham, N. Accuracy and stability of numerical algorithms / N. Higham // Philadelphia: Society for Industrial and Applied Mathematics. 1996.

44. Hong, H. Private communication / H. Hong // RISC-Linz, Austria.

45. Koelbel, C. The High Performance Fortran Handbook / C. Koelbel, D. Loveman, R. Schreiber, G. Steele, M. Zosel // MIT Press. 1993.

46. Kumar, V. Introduction to Parallel Computing / V. Kumar, A. Grama, A. Gupta, G. Karypis // The Benjamin/Cummings Publishing Company, Inc. -1994.

47. Lipson, J. Elements of Algebra and Algebraic Computing / J. Lipson // Benjamin Cumming. 1984.

48. Maeder, R. Storage allocation for the Karatsuba integer multiplication algorithm / R. Maeder // In Alfonso Miola editor Design and Implementation of Symbolic Computation Systems. DISCO 93 volume 722 of LNCS. -1993.-pp. 59-65.

49. Metcalf, M. Fortran 90 explained / M. Metcalf, J. Reid // Oxford University Press. 1990.

50. MPI. A Message-Passing Interface Standard. Message Passing Interface Forum. -1994.

51. PVM 3. User's guide and reference manual. 1994.

52. Saad, Y. Iterative Methods for Sparse Linear Sestems / Y. Saad // NY:PWS Publish. 1996.

53. Schonhage, A. A multitape Turing machine implementation / A. Schon-hage, A. Grotefeld, E. Vetter // Bl-Wissenschaftsverlag. 1994.

54. Traverso, C. Grobner trace algorithms / C. Traverso // Springer-Verlag. -1988.-pp. 125-138.

55. Van Loan, C. Computational frameworks for the fast Fourier transform / C. Van Loan // volume 10 of Frontiers in applied mathematics. Philadelphia: Society for Industrial and Applied Mathematics. 1992.

56. Wachspress, E. L. Extended application of alternating direction model problem theory / E. L. Wachspress // J.Soc. Indust. Appl. Math. 1963. -v. 11.-N4.-394-1015.

57. Wachspress, E. L. Optimum Alternating-Direction-Implicit Parameters for a model problem / E. L. Wachspress // J.Soc. Indust. Appl. Math. -1962. v. 10. - N 2- 339-350.

58. Wang, P. S. A p-adic algorithm for univariate partial fractions / P. S. Wang // ACM Press. 1981. - pp. 212-217

59. Wang, P. S. Early detection of true factors in univariate polynomial factorization / P. S. Wang // Springer-Verlag. -1983. pp. 225-235.