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

• Германенко, Максим Игоревич
• кандидат физико-математических наук
• 2009

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

ВВЕДЕНИЕ.

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. Разработанные классы адаптированы для параллельных вычислений. Проведен анализ ускорения использования параллельных вычислений для решения данных задач.

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

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.