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

Тамбовский государственный университет имени Г Р Державина

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

¡у*

Зуев Михаил Сергеевич

МАТРИЧНЫЕ АЛГОРИТМЫ КОМПЬЮТЕРНОЙ АЛГЕБРЫ ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

рНЯР

Тамбов 2007

Работа выполнена в лаборатории алгебраических вычислений Тамбовского государственного университета им Г Р Державина

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

профессор

Малашонок Геннадий Иванович

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

профессор

Абрамов Сергей Александрович

Защита диссертации состоится « 21 » декабря 2007 г в 15 часов на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, г Москва, ул Большая Коммунистическая, 25, Институт системного программирования РАН, конференц-зал

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан « 20 » ноября 2007 г

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

кандидат физико-математических наук

Шокуров Александр Владимирович

Ведущая организация Механико-математический факультет

Московского государственного университета им М В Ломоносова

/Прохоров СП/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертационная работа посвящена разработке эффективных алгоритмов для матриц над полями и коммутативными областями

Актуальность темы.

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

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

Одним из главных препятствий для использования известных блочных матричных алгоритмов является возможность вырождения ведущего блока При этом алгоритм должен либо прекратить работу, либо должна произойти реорганизация вычислений, уменьшающая количество его параллельных инструкций Отметим, что С Ватт1 предлагает обращать матрицу Ат А, у которой все главные миноры невырожденные, а затем вычислять А-1 = (АтА)~1 Ат Но за это ему приходится расплачиваться дополнительными двумя матричными умножениями

Цель работы.

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

1Watt S M Pivot-Free Block Matrix Inversion Proc 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, (SYNASC 2006), Sept 26-29 2006, Timisoara, Romania

алгоритмов Сюда относятся следующие задачи

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

• Обращение матриц над полем Нахождение и обращение максимальной невырожденной подматрицы для вырожденной матрицы

• Решение неопределенных систем над полем

• Построение эффективных форматов хранения матриц для блочно-рекурсивных и параллельных алгоритмов

• Получение оценок сложности для алгоритмов умножения разреженных числовых и полиномиальных матриц

Методы исследования.

В работе используются методы компьютерной алгебры, в том числе методы гомоморфных образов, методы детерминантных тождеств, а также методы теории графов и теории вероятностей Для экспериментов использовались пакеты JDK текущих версий, а для экспериментов с параллельными алгоритмами - среда Par Java ИСП РАН

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

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

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

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

Практическая ценность.

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

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

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

- Алгебра и анализ (Казань, 2004),

- 6 Международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004),

- Проблемы теоретической кибернетики (Пенза, 2005),

- Державинские чтения (Тамбов, 2004—2007),

- 12-я международная конференция, посвященная приложениям компьютерной алгебры (Варна, Болгария, 2006),

- научные семинары в Тамбовском университете

Публикации автора. Основные результаты диссертации опубликованы в 14 работах

Структура и объем работы Диссертация состоит из введения, четырех глав, включающих 11 параграфов, заключения, приложения, списка литерат>ры и изложена на 138 страницах

СОДЕРЖАНИЕ РАБОТЫ

Во введении сформулирована цель работы, дан обзор близких работ и кратко изложено содержание диссертации

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

• ~ блок матрицы А, стоящий на пересечении ее строк с номерами к,к + 1, ,1 и столбцов с номерами т,т + 1, — 1 и0^т<п<ЛГ-1),

• ак - верхний левый угловой ыинор матрицы А порядка к, положено а° = 1

• - минор порядка к, полученный окаймлением верхнего левого углового минора матрицы А порядка к — 1 строкой г и столбцом ], в частности, а,1^ =

• Ак = (а?3) - матрица, составленная из миноров а^, в частности, А1 = А

• А" - присоединенная матрица к матрице А

Известен алгоритм2, который вычисляет присоединенную матрицу

/ Ао,к-1 с \

и определитель для невырожденной матрицы А = I £> I ^

RNxN , блоки /lg'^I J и D которой квадратные и невырожденные В его основе лежит формула для факторизации присоединенной матрицы А*

( -(a^FC \ ( I 0 \ ( I 0 \ ( F 0 \

V О I ) \ О G ) \ -В akI ) \ О I ) '

где F = A°0izV, а* = detA^I^, G = (a*)-^«^^-1*, "" = (a'!)-N+'t+2det4+1lfciN-1, a A^N-i^1 = *kD - BFC Этот алгоритм находит присоединенную матрицу и определитель только в случае, когда левые угловые миноры четного порядка ненулевые

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

В его основе лежат следующие предложения

1 Пилотируемость Предлагается управлять выбором диагонального минора .Д^-!*"-1 путем умножения на матрицу перестановок Для этого производятся эффективные вычисления матрицы -^^ч".!™1-1, где mi > тп и поиск в ней невырожденной подматрицы требуемого ранга

2 Отказ от локально-блочной рекурсивности Эффективные вычисления блока -^slmi^-T1 на некотором шаге алгоритма используют подматрицы с предыдущих шагов При этом необходимость обращать на каждом шаге матрицы малого порядка алгоритмически упрощает задачу поиска невырожденной подматрицы в блоке -Т1"1

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

Пусть F - поле, полугруппа Рп образована матрицами над F порядка n, у которых число единичных элементов совпадает с рангом матрицы, а остальные элементы равны нулю Полугруппа Dn образована диагональными матрицами порядка п с элементами 0 и 1 на диагонали, \Dn\—2n и

2см Malaschonok G. I. Effective Matrix Methods in Commutative Domains / Formal Power Series and Algebraic Combinatorics Springer, 2000 P 506-517

единичная матрица I - единица в Оп и в Рп Чертой обозначена инволюция на Оп I = I — I, в частности II = О

П}сть п = 2к Алгоритм обращения матриц с двусторонним разложением вычисляет две обратимые матрицы Ли С для произвольной матрицы А £ Гпхп, такие что НАС = Е £ Рп Если А = 1АЗ и 1,3 £ £>„, то Я = 7 + 1Ш, С = 3 + ЗЯЗ, Е = 1ЕЗ Если А - обратима, то ЕТЕ = I и А"1 = СЕТП

Если матрица А второго порядка, то требуемые матрицы ИиС легко найти П>сть матрица А порядка 2п, разбита на равные блоки

Ап А\2 А21 А2 2

1 Рекурсивный шаг вычисляются такие обратимые матрицы Лц и Сц, что ДцАцСц = Ей 6 Рп Найдено Я1АС1 = А1, где

В1 = ( Пи 0 ^ С1 = ( Сп ~СпЕ"а

-/ЗЕЬДи I ) ' 1 V 0 1 Здесь /1 = Ей Ей, 3\ = Е^Ец, а = Л11А12, /3 = А21С11,

А1 = ( ¿Ь А\2 \ = ( Е±1 Ъа V ¿21 А\2 ) \ 03! А22-0ЕТ1а

2 Параллельно выполняемые рекурсивные шаги вычисляются тамге обратимые матрицы Л12, С12, Д21, С21, что ДхгА^СЪ =_ Е\2_а Д21А21С21 = Е21 При этом В. 12 = /1_+ 7\В.\27\, С21 = 3\ + З1С21З1, а матрицы Е\2 и Е2\ имеют вид £12 = /1^12 6 Рп, Е21 = Е21З1 £ Рп Найдено К2АХС2 = А2, где

П2 - ( -7£&Я13 Д21 ) ' Сг - (

С21 —С2\Е~2\~13\2

О С12

Обозначено Л2 = Е^Еп, /21 = £21 £211 7 = Н-2\А\2С\2, *2_ ( А\х А\г \ _ ( Ец Е12

А ' ¿21 ¿22 ) V /217^12

Использованы тождества ЕцЗ\ = Ец и 1\Ец = -Ец, ЕцЗ\ = О, 71 = О, Е12Е11 = 0, ЕпЕ1| = О

3 Рекурсивный шаг вычисляются такие обратимые матрицы Я22 и С22, чт0 -йггАггСи = Е22, при этом £22 = 121Е22З12 £ Рп, И22 = + 121Р-22121 И С22 = З12 + 312022 312

Найдено ИзЛ2Сз = Е, где

Лз = ( О L ) ' Сз - ( о С22 ) ' Е~ ( Ehi Ell ) В результате получены RAC = Е, где

fí=f R12R11 О N

V -R22(jE'[2Ri2+R2ißE'[1)Ru R22R21 ) '

q _ ( C11C21 —Cu(C2iE2i'yJi2 + Ei1aCi2)C22 \ \ О С12С22 )

Двусторонний алгоритм использует 17 матричных умножений и 4 рекурсивных вызова в общем случае Если упР + о{рР) - сложность матричного умножения, то сложность вычисления матриц ДиС для матрицы размера п — 2т с помощью двустороннего алгоритма не превосходит 177 ^ гД-/"2 + 5п + о(рР) операций умножения В частности, при применении стандартного алгоритма умножения сложность не превосходит 17/4(п3-2п2) + 5п, при применении алгоритма Штрассена сложность не превосходит 17/3(п1оЭ27 - 7/4га2) + 5га

В случае, когда левый верхний и правый нижний блоки матрицы невырождены, используются 7 матричных умножений и 2 рекурсивных вызова алгоритма Если это справедливо и при рекурсивных вызовах алгоритма, то сложность вычислений не выше 77"й~^2 " +5га + o{vP) В частности, при применении стандартного алгоритма умножения сложность равна 7/6(п3 — 4га) + 5га, при применении алгоритма Штрассена сложность равна 7/5(raloff2r _ 7/2п) + 5п

Для формулировки второго алгоритма вводится новый канонический вид матриц Матрица Я 6 Fnxn имеет главную часть Е е Рп, если Я = IH и Е = HJ, где I = ЕЕТ 6 Dn и J = ЕТЕ 6 Dn> другими словами, множества нулевых строк у матриц Н и Е совпадают, и все ненулевые столбцы Е содержатся в Я В частности, если Я обратима, то Е = Я 6 Рп Ненулевые столбцы матрицы Е называются главными столбцами матриц Е и Я

Алгоритм с односторонним разложением приводит матрицу к такому каноническому виду Для матрицы А € Fnxn вычисляется такая обратимая матрица R = R(A), что RA = Я, при этом Я - это матрица с некоторой главной частью Е € Рп Если матрица А имеет вид А = IA, I € Dn, то R имеет вид R = I + IRI и, следовательно, Я = IH Если А -обратима, то ЯТЯ = I и A~l = HTR

Если матрица А второго порядка, то легко предъявить требуемую матрицу Л Пусть матрица А порядка 2п = 2к, к > 1, разбита на равные блоки п х п

Ап А12 Л21 А22

1 Рекурсивный шаг Ли = Л(Ац) При этом ДцЛц = Ни с главной частью Ец Обозначено = Ей Ей, /п = Ей Ей Вычислено

Здесь

; Го"

Ail А\2\ ( Я11 Ru Au

AnÇL-E&Hu) А22 - A21EllA\2

Так как в матрице I—Ей Ни нулевыми являются все главные столбцы Ец, то выполняется Ah = A\iJu

2 Параллельные рекурсии Я12 = Ri1î(A\2) и Л21 = R{A\ 1) При этом RuInA\2 = H12 с главной частью Е12 и Л21А21 = Я21 с главной частью Е21 Обозначено J12 = Ej2E\2, J21 = Е21Е21, h2 = £i2ëL £21 = Е21Е21, А22 = Я21А22

Вычислено = Л2, где матрица R2 образована произведением

I -AhEZ \( I 0 \ / I - 1пА\2ЕТ2 О

о i А -а&ЕТ2 I ) \ О I

Rl2 О О Ли

(I — IuA\2Ei2 + Au E21 Al2Ej~2)Rl2 —A11E21R21 —A22EJ2Ri2 Л21

Получены тождества_Ях2 =_IuHi2, h\Ei2 — 0, E?2Iu = 0, и тот факт, что из R12 = lu + InRnïu и Ни = hiHu следует Л12Я11 = Ни, Ef2R12Hи = ЕТ21иНи = 0, E&fliaAb = Ef2iîi2(/ii + hi)A\2 = Ef2hiA\2 + EJ2H12 = Е12Н12, следовательно = Яц(I - Е^Нц), A2i — Я21,

А?2 = Д12Л}2 + (-7ЦА}2 + ¿Ь-Е&ЛЙ^Ям - ¿hJSMS = Я12 + /ц-412 - InAliE&Hu + AI-LÉ&A&ÎÉ&Hii - I) = Я12 + {1пА\2 -AhE&A&XI-E&Hn),

А22 = А2г(1 — Е12Н12) ^

При этом выполняются равенства А\г = AuJ2i, А21 = A2i Ji, А\2 — Е12 = (Ai2 — £l2)Jl2, A22 = A22 Jl2,

R2

3 Рекурсивный шаг R22 = Ril2(Al2) При ЭТОМ R22I12A22 = Я22 С

главной частью £22 Обозначено J22 Вычислено

: Е22Е22, I22 = Е22Е2

R3A2

—А12Е22 I

Дз

(5

О I — I21A22E22

— A12E22R22 (I — /21 ^22^22)-^-22

I О

О R2 2

Л

л3,

где = = А221, А312 = Л?2(1 - EJ2R22AI2) = А\2{I -

Л22 = Яг2 + /21^22(1 — Е22H22) и выполняются равенства Af2 = A\2J22, А22 — £22 = (Л22 — E22)J 22 Обозначено

М= (1-/21^2^2)Й22,

G = R2I(A122ET2Ri2 + AllEfORu В результате получено RA = H -

-(

£12 £22

где R -

Ей

Е21

Здесь

А\2 = iîn/li2, ¿21 = A21(I-EÏlH11), А\2 = А22 - A21ET1AI2,

L+FG -MG

А3п А321

-FR21

M Ri 1

^12

с главной частью

' Е±2Н\2),

A\2=R2lA\3{ I-

л?2 = я12 + /иЛ}2(1 - £;Г2я12) - HuE^Ah

Односторонний алгоритм использует 21 матричное умножение и 4 рекурсивных вызова в общем случае Сложность вычислений с односторонним алгоритмом не превосходит 21-у n0~22f_*7,2 + о{п0) В частности, при применении стандартного алгоритма умножения сложность не превосходит 21/4(гг3 — 2га2)+ 5п, при применении алгоритма Штрассена сложность не превосходит 7(га'°327 - 7/4тг2) + 5га

В случае, когда левый верхний и правый нижний блоки матрицы невырождены, используются 6 матричных умножений и 2 рекурсивных вызова алгоритма Если это справедливо и при рекурсивных вызовах алгоритма, то сложность вычислений не превосходит 67 21 " + 5га + о(пВ частности, при применении стандартного алгоритма умножения сложность не превосходит га3 + га, при применении алгоритма Штрассена сложность не превосходит 6/5п1°327 + А/Ьтг

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

Форматом хранения матрицы называется способ ее представления в памяти машины Существует несколько десятков форматов хранения разреженных матриц В этой главе используются три формата хранения разреженных матриц - QT(quaternary tree), SM (sparse matrix) и QTSM (quaternary tree of sparse matrices)

Хранение матриц в виде кватернарного дерева (QT) применялось еще в работе Д С Вайза3 Оно основано на дихотомическом делении всех строк и столбцов матриц четного порядка В результате такого деления образуются четыре равных блока Если матрица имеет порядок 2П, то каждый блок снова делится на 4 подблока, и так далее Наименьшим блоком является блок размера 1x1

Соответствующее этой матрице дерево строится следующим образом Когда все четыре блока матрицы ненулевые, то из корневой вершины исходят четыре ребра Эти ребра нумеруются 0,1,2,3, где первый двоичный разряд числа - это номер блочной строки, второй двоичный разряд - номер блочного столбца Аналогично для подблоков Если некоторый блок нулевой, то соответствующее ему ребро в дереве отсутствует

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

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

Приведены результаты некоторых вычислительных экспериментов с новым форматом В частности, приведены эксперименты для алгоритма стандартного умножения Плотность сомножителей изменялась от 1 до 100 % с шагом 10 Для умножения матриц порядка 512 над 32-битными целыми числами лучшими алгоритмами являются блочное DM-умножение, SM-умножение и QTSM-умножение Если сумма плотностей сомножите-

Зсм Abdali S.K., Wise D S. Experiments with quadtree representation of matrices Proc ISSAC 88, Lecture Notes in Computer Science 358, Springer Verlag, 1989, P 96-108

лей не ниже 100 % и плотность левого сомножителя не ниже 50 %, то лучшим алгоритмом является блочный DM-алгоритм, при этом QTSM-алгоритм проигрывает ему не более чем на 20 % Если плотность правого сомножителя изменяется в интервале 10-20%, а левого - в интервале 20-90 %, лучшим является SM-алгоритм, при этом QTSM-алгоритм проигрывает ему не более чем на 12 % В остальных случаях лучшим алгоритмом является алгоритм QTSM-умножения, которому алгоритм DM проигрывает до 99 раз и алгоритм SM до 2 раз

Проведены эксперименты с односторонним алгоритмом (см главу 2) обращения матриц порядка 64-1024 по простому модулю Сравнивались форматы DM и QTSM Эксперименты показали, что для невырожденных матриц с невырожденными диагональными блоками наиболее эффективен формат DM, а для вырожденных - QTSM

Сравнение алгоритмов умножения плотных матриц порядка 4096 показало эффективность блочно-рекурсивных процедур Лучшим оказался алгоритм Штрассена с листом порядка 128, для которого выполняется умножение обычным способом Он работает быстрее стандартного алгоритма в 16 4 раз и алгоритма Штрассена в 10 7 раз В данном эксперименте также исследовались алгоритмы, использующие запись блоков матриц на диск Матрица разбивается на блоки фиксированного размера, каждый из которых записывается в отдельный файл на жесткий диск Эта идея записи матриц использовалась в пакете POOCLAPACK4 В данной работе рассматривается возможность хранить блоки матрицы в отдельных папках Среди таких алгоритмов лучшим оказался алгоритм Штрассена с листом порядка 2048 и записью на диск блоков порядка 128 Он проигрывает лучшему алгоритму по времени в 1 6 раз Худшими оказались блочные алгоритмы стандартного умножения, не использующие диск для записи блоков

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

Определение 1. Полиномом типа (m, av) называется полином

4Reiley W. С., van de Geijn R. A. POOCLAPACK Parallel Out-of-Core Linear Algebra Package //Technical report CS-TR-99-33 Austin, TX, USA University of Texas at Austin, 1999

с"е у которого коэффициент Си отличен от нуля с ве-

роятностью ау Если аь = а для всех V, то тип полинома обозначен (т,а) Число а называется плотностью полинома Полином (т, а„) не равен нулю с вероятностью к(т, а„) = 1 — (1 частном случае

к(т,а) = 1 — (1 — а)т

Определение 2. Матрицей типа (п, р,т,а.к) называется случайная матрица размера п х п, каждый элемент которой отличен от нуля с вероятностью р, а каждый ненулевой элемент - это полином типа (т, а к) Обозначено £ А и ЕМ. математическое ожидание числа операций сложения и умножения в алгоритме, а также ф(а, Ь) = а + Ь — аЬ

Для полиномиальных алгоритмов сложения и стандартного умножения справедливо

(7п, а,) + (т,/3.) = (т,ф{аг,р,))

(■т,а) х (т,/3) = (2т - 1,тгГ(а,/?))

£А({т, а) + (т, ¡3)) = та/3, (1)

£М({т, а) х (т,/3)) = т2а/3, £А({т,а) х (тп,/3)) = (т - 1)2а/3,

где

1т — [ 1 при * ^ г ^ т г \ 2тп — г при т < г ^ 2т — 1

и

тг,т(а,/3) = 1-(1-а|9)С

Для матричных алгоритмов сложения и стандартного умножения справедливо

(п,р,т,ау) + (п,а,т,ру) = (п,ф(р,а),т,ф(ра^,а/Зу))

т

£А = п2ра ^У^^осуРу

и=1

(п, р, т, а) х (гг, а, т, 0) = (п, 1 — (1 — рст)", 2т — 1,77„) = n3qM

2т-1

^ = п3дЛ + гг2 £ ((1-д7гЛа,/?))п-1+п<?7С(а,/?)),

где

Й = = = 1 - (1 - а„)к+1,

Ч» = Е Скпдк( 1 - - (1 - тС(а,0))к) = 1 - (1 - дп™(а,0)Г

к=1

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

В заключении сформулированы основные результаты работы

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

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

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

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

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

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

Статьи в изданиях по перечню ВАК1

1 Зуев М С Быстрые алгоритмы деления починомов // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2004 Т 9, вып 1 С 150-152

2 Зуев М С Пилотируемый алгоритм вычисления присоединенной матрицы и определителя // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2006 Т 11, вып 4 С 550-554

3 Малашонок Г И , Валеев Ю Д , Зуев М С О параллельных матричных алгоритмах в компьютерной алгебре // Вестник Тамб унта Сер Естеств и техн науки Тамбов, 2005 Т 10, вып 1 С 102104

4 Малашонок Г И , Зуев М С О представлении матриц кватернар-ными деревьями // Вестник Тамб ун-та Сер Естеств и техн на-у ки Тамбов, 2005 Т 10, вып 1 С 98-100

о Зуев М С Сложность алгоритмов для разреженных полиномиальных матриц // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2007 Т 12, вып 1 С 131

Учебные пособия

6 Малашонок Г И , Валеёв Ю Д , Зуев М С Параллечьные вычисления на бинарных деревьях в задачах компьютерной алгебры Тамбов Изд-во ТГУ им Г Р Державина, 2006 122 с

7 Малашонок Г И , Валеев Ю Д , Зуев М С Параллельная компьютерная алгебра Введение Тамбов Изд-во ТГУ им Г Р Державина, 2006 102 с

Прочие публикации-

8 Зуев М С О сложности алгоритмов умножения матриц над полиномами // XIV Междунар конф "Проблемы теоретической кибернетики" Тез докл М Изд-во механико-математического факультета МГУ, 2005 С 52

9 Зуев М С Об истории параллельных матричных алгоритмов // Современное математическое образование и проблемы истории и методологии науки Тамбов Изд-во Першина Р В , 2006 С 118-124

10 Зуев М С Пилотируемый алгоритм вычисления присоединенной матрицы в коммутативной области // Труды Математического центра им Н И Лобачевского Т 23 Казань Изд-во Казанского математического общества, 2004 С 51-52

11 Зуев M С , Малашонок Г И О сложности алгоритмов умножения полиномиальных матриц // Труды 6 Междунар конф "Дискретные модели в теории управляющих систем" M Изд-во ВМиК МГУ, 2004 С 32-40

12 Малашонок Г И , Аветисян А И , Валеев Ю Д, Зуев M С Параллельные алгоритмы компьютерной алгебры // Труды Института Системного Программирования / под ред В П Иванникова M ИСП РАН, 2004 С 169-180

13 Малашонок Г И , Зуев M С Обобщенный алгоритм вычисления обратной матрицы //XI Державинские чтения Тез докл Тамбов Изд-во ТГУ им Г Р Державина, 2006 С 48-50

14 Malaschonok G I, Valeev Y D , Zuyev M S , Kazakov V N On the parallel computer algebra // АСА 2006 12th International Conference on Applications of Computer Algebra Institute of Mathematics and Informatics Bulgarian Academy of Sciences (June 26-29, 2006, Varna, Bulgaria ) Sofia, 2006 P 52

Подписано в печать 15 11 2007 г Формат 60 х 48/16 Объем 1,0 п л Тираж 100 экз Заказ № 1156 Бесплатно 392008, г Тамбов, Советская, 190г Издательство ТГУ им Г Р Державина