Содержание к диссертации
Введение
1 Методы вычисления характеристических полиномов в коммутативных областях 15
1.1. Метод Леверье 16
1.2. Метод Леверье-Фаддеева 19
1.3. Метод Чистова 21
1.4. Алгоритм Берковича 22
1.5. Алгоритм Сейфуллина 24
1.6. Алгоритм Малашонка 29
1.7. Новый алгоритм 32
1.8. Выводы 34
2 Алгоритмы вычисления характеристических полино мов матриц в кольце целых чисел и в кольце полиномов с целыми коэффициентами 36
2.1. Сложность алгоритмов, выраженная в числе машинных операций 37
2.1.1. Метод Леверье 37
2.1.2. Метод Леверье-Винограда 38
2.1.3. Алгоритм Леверье-Фаддеева 39
2.1.4. Алгоритм Чистова 40
2.1.5. Алгоритм Берковича 41
2.1.6. Алгоритм Сейфуллина 42
2.1.7. Алгоритм Малашонка и новый алгоритм
2.2. Метод Данилевского 47
2.3. Применение метода гомоморфных образов для вычисления характеристических полиномов матриц в кольце целых чисел 50
2.4. Экспериментальное сравнение алгоритмов в кольце целых чисел 51
2.5. Вычисление характеристических полиномов полиномиальных матриц
2.5.1. Применение метода гомоморфных образов для вычисления характеристических полипомов полиномиальных матриц 56
2.5.2. Оценка коэффициентов характеристического полинома полиномиальной матрицы 57
2.5.3. Алгоритм, основанный на методе гомоморфных образов, который в конечном поле использует алгоритм Данилевского 59
2.5.4. Вычислительные эксперименты 60
2.6. Выводы 61
3 Параллельные алгоритмы вычисления характеристических полиномов 64
3.1. Параллельный алгоритм вычисления характеристических полиномов для целочисленных матриц с восстановлением по бинарному дереву 65
3.1.1. Алгоритм 65
3.1.2. Результаты экспериментов 66
3.2. Параллельный алгоритм вычисления характеристического полинома для полиномиальных матриц с восстановлением по бинарному дереву 69
3.2.1. Схема передачи данных 69
3.2.2. Алгоритм вычисления характеристического полинома полиномиальной матрицы 72
3.2.3. Пример в кольце полиномов от двух переменных 74
3.2.4. Эксперименты 79
3.3. Параллельный алгоритм вычисления характеристического по линома с восстановлением на листовых вершинах 81
3.3.1. Алгоритм 81
3.3.2. Время вычисления характеристического полинома 83
3.3.3. Эксперименты 86
3.4. Выводы 93
Заключение 94
Приложение 95
Приложение 1. Алгоритмы, описанные в главе 1 95
Приложение 2. Алгоритм, описанный в параграфе 2 главы 3 101
Приложение 3. Алгоритм, описанный в параграфе 3 главы 3 107
Литература
- Алгоритм Берковича
- Алгоритм Леверье-Фаддеева
- Вычисление характеристических полиномов полиномиальных матриц
- Алгоритм вычисления характеристического полинома полиномиальной матрицы
Введение к работе
Диссертационная работа посвящена разработке эффективных последовательных и параллельных алгоритмов вычисления характеристических полиномов плотных матриц. Изучаются алгоритмы как для матриц над коммутативными кольцами и областями общего вида, так и для матриц над областями целых чисел и полиномов многих переменных.
Актуальность темы.
Характеристические полиномы матриц впервые появляются в трудах Лапласа, Якоби и Леверье. За прошедшие полтора столетия они нашли приложения в самых разных теоретических и прикладных областях - в теории матриц, в терии представлений групп, в механике, в астрономии, в физике, химии, биологии, во многих технических задачах, в теории управления.
Один из первых методов вычисления характеристических полиномов матриц в коммутативном, кольце предложил в 1881 г. Леверье. Видоизменение этого метода, предложенное в 1943 г. Фаддеевым Д.К., позволило вычислять одновременно еще и присоединенную матрицу. Алгоритм Леверье (с улучшением Винограда) требует выполнения — 4те3'кольцевых операций, алгоритм Фаддеева — — 2n кольцевых операций при вычислении характеристического полинома матрицы размера n х n. В основе алгоритмов лежит вычисление произведения матриц. Это позволяет для распараллеливания этих алгоритмов использовать параллельное умножение матриц.
Отметим недавно полученные алгоритмы для коммутативных областей. Алгоритм Сейфуллина4 (2002) требует кольцевых операций - 1/2n4. Алгор итм Малашонка (1999) и новый алгоритм (2008) требуют, соответственно, — 8/3n3 и — 7/3n3 кольцевых операций.
В работе Икрамова Х.Д. как наиболее эффективный способ точного вычисления характеристического многочлена матриц над конечными полями рекомендуется метод Данилевского (1937), который требует выполнения ~ 2п3 операций. Асимптотически лучшими последовательными алгоритмами для вычисления характеристического полинома в конечном поле являются алгоритм Келлер-Гехрига (1985) и вероятностный алгоритм Пернета-Сторьоханна (2007), которые требуют выполнения (пш Iog2 n) и (пш) операций соответственно. Здесь (пш) обозначает сложность матричного умножения.
После публикации [2, 16, 17, 18] в российских научных изданиях работ автора, в которых предлагаются новые алгоритмы и методы рас- спараллеливания алгоритмов вычисления характеристических полиномов, появился ряд статей по этой же теме других авторов. Так японские математики К. Kumura и Н. Anai предлагают алгоритм вычисления определителя с использованием модулярной арифметики. Они приводят результаты экспериментов на 2-х процессорном компьютере и демонстрируют ускорение по сравнению с системами Maple 13 и Mathematica 6.
Французские математики Ф. Обри и А. Валибуз предложили параллельный алгоритм вычисления резольвенты Лагранжа для полинома одной переменной с использованием техники модулярных вычислений. Они получили формулу для разложения резольвент, которая позволяет строить параллельные алгоритмы с двумя уровнями распараллеливания. В работе других французских авторов J.-G. Dumas, Th. Gautier и J.-L. Roch описывается схема распараллеливания алгоритмов вычисления определителя и характеристического полинома матриц с применением модулярных вычислений.
Цель работы.
Цель диссертационной работы состоит в разработке последовательных и параллельных алгоритмов вычисления характеристических полиномов плотных матриц над целыми числами и над полиномами многих переменных с целыми коэффициентами.
Задачи работы.
Для известных алгоритмов вычисления характеристических полиномов матриц требуется получить уточненные выражения, характеризующие сложность этих алгоритмов.
характеристических полиномов матриц в коммутативных областях.
характеристических полиномов целочисленных и полиномиальных матриц.
ристического полинома для целочисленных матриц и матриц над полиномами многих переменных.
сти полученных алгоритмов и программ.
Научная новизна.
Получены теоретические выражения, характеризующие сложность алгоритмов вычисления характеристических полиномов матриц в коммутативной области и в кольце целых чисел. Полученные выражения для количества мультипликативных операций в машинных словах позволяют выбрать лучший алгоритм.
Разработан новый эффективный алгоритм для вычисления характеристических полиномов матриц в коммутативных областях. Алгоритм имеет наименьшее число аддитивных и мультипликативных операций среди известных алгоритмов.
Разработан параллельный метод вычисления характеристических полиномов с использованием модулярной арифметики.
Разработаны и исследованы новые параллельные алгоритмы и программы для вычисления характеристических полиномов матриц в кольце целых чисел и в кольце полиномов с целыми коэффициентами.
Практическая значимость.
Разработанные алгоритмы и программы могут использоваться в пакетах прикладных программ и системах компьютерной алгебры. Разработанные алгоритмы входят в учебные пособия, изданные для студентов Тамбовского государственного университета им. Г.Р.Державина, и используются в учебных курсах по компьютерной алгебре, параллельному программированию и по параллельной компьютерной алгебре.
Апробация работы.
Результаты исследований докладывались на Международных научных конференциях Parallel Computer Algebra (РагСА'2010) (Тамбов, 29 июня - 3 июля 2010), Polynomial Computer Algebra (Санкт-Петербург, 4-7 апреля 2008, 8-12 апреля 2009, 2-7 апреля 2010, 17-22 апреля 2011, 23-28 апреля 2012), ПаВТ'2009 (Нижний Новгород, 30 марта - 3 апреля 2009), Mathematical Modeling and Computational Physics (MMCP'2009) (Dubna, July 7-11, 2009), Колмогоровские чтения. Общие проблемы управления и их приложения (ОПУ-2009) (Тамбов 5-9 октября 2009), "Современное математическое образование и проблемы истории и методологии математики" (Тамбов, 2006, 2008), Державин- ские чтения (Тамбов, 2005—2012), научном семинаре «Компьютерная алгебра» факультета BMK МГУ и ВЦ РАН, научных семинарах в Тамбовском государственном университете.
Публикации автора. Основные результаты диссертации опубликованы в 20 научных работах автора (все работы без соавторов, из них 10 работ опубликованы в журналах, которые входят в список журналов, рекомендованных ВАК РФ) и двух учебных пособиях, в которых автором написаны отдельные главы.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, библиографии и трех приложений. Общий объем диссертации составляет 117 страниц, включая 23 рисунка, 7 таблиц. Библиография включает 56 наименований.
Алгоритм Берковича
Результаты проведенных экспериментов с прямыми алгоритмами хорошо согласуются с выводами, сделанными на основе теоретических оценок из таблицы 2.
Во 2-м параграфе исследуется алгоритм Данилевского. В этом алгоритме требуется выполнить 2п3 — Ъп2 + 6п — 3 операций в поле К.
Алгоритм Данилевского состоит из п шагов, в результате которых вычисляется матрица, подобная данной, в форме Фробениуса. Элементы последнего столбца полученной матрицы являются коэффициентами характеристического полинома.
В 3-м параграфе исследуются методы вычисления характеристических полиномов целочисленных матриц, в которых используется метод гомоморфных образов. Приводится сравнение с прямыми методами. Обсуждаются результаты экспериментов.
Эксперименты подтвердили, что лучшее время вычислений показывает метод гомоморфных образов, в котором используется метод Данилевского для конечных полей. Однако для матриц небольших размеров (не более, чем 35 х 35) прямой метод Сейфуллина является наилучшим (см. рис. 3).
Эксперименты показали, что алгоритм, основанный па методе гомоморфных образов, в котором в конечном поле используется алгоритм Данилевского, вычисляет характеристический полином существенно быстрее, чем Maple 9.5 и Mathematica 7.0. Например, для Ь = 7 и п = 50 Mathematica проигрывает в 5,9 раза, a Maple проигрывает в 11,5 раза. Для п = 100 алгоритм, основанный на методе гомоморфных образов, быстрее, чем Mathematica в 13,1 раз и быстрее, чем Maple в 13,8 раз, а для п = 200 — в 26 и 16 раз соответственно.
В 4-м параграфе рассматривается алгоритм вычисления характеристических полиномов матриц, основанный на методе гомоморфных образов, в кольце полиномов с целыми коэффициентами.
Составной частью алгоритма является вычисление верхней оценки наибольшего по абсолютной величине числового коэффициента характеристического полинома. Для вычисления такой оценки была доказана теорема.
Обозначим для полиномад через \\д\\ — наибольший по абсолютной величине числовой коэффициент этого полинома и s(g) — количество мономов в полиноме д.
Экспериментальное сравнение алгоритмов вычисления характеристических полиномов для полиномиальных матриц показало, что алгоритм, основанный па методе гомоморфных образов, в котором для вычисления характеристического полинома в конечном поле используется алгоритм Данилевского, выигрывает у остальных рассматриваемых алгоритмов. Кроме того, ом быстрее алгоритма, реализованного в системе Mathematica. Например, если порядок матрицы п = 20 и степень входных полиномов d — 15, он вычисляет характеристический полипом быстрее в 23 раза, чем алгоритм, который реализован в системе Mathematica 7.0.
В 3-й главе рассматриваются параллельные алгоритмы вычисления характеристических полипомов матриц. В основе схемы распараллеливания лежит метод гомоморфных образов, применяемый как к кольцам полиномов многих переменных, так и к кольцу целых чисел. В этой главе рассматривается 2 типа задач — вычисление характеристического полипома для числовой матрицы и вычисление характеристического полинома для полиномиальной матрицы. Исследуются два параллельных алгоритма, основанных на методе гомоморфных образов. Они отличаются графом параллельного алгоритма. В первом случае используется бинарное дерево, а во втором — дерево, которое состоит только из корневой вершины и листовых вершин, каждая из которых связана ребром с корневой вершиной.
В 1-м параграфе описывается параллельный алгоритм вычисления характеристических полиномов матриц для кольца целых чисел. Раздача простых модулей происходит по бинарному дереву. Для этого при переходе на следующий уровень дерева процессор делит отрезок номеров числовых модулей [ЇЇ; І2І на два отрезка [h\j\ и [j + 1; І2], где j = (і\ + гг)/2. Один отрезок он оставляет себе, а второй передает свободному процессору. Процесс бинарного деления останавливается, когда исчерпываются или процессоры или модули. На листовых вершинах вычисляются характеристические полиномы по простым модулям. Восстановление полинома происходит при подъеме от листовых вершин к корневой вершине па каждом узле бинарного дерева.
Графики зависимости времени вычисления от количества процессоров носят ступенчатый характер. Скачкообразное уменьшение времени вычисления наблюдается, когда количество процессоров кратно 2Р, где р — натуральное число. Наилучшее ускорение достигается, если количество процессоров является степенью числа 2.
Во 2-м параграфе описывается алгоритм вычисления характеристических полиномов полиномиальных матриц, граф которого представляет собой бинарное дерево. Этот алгоритм аналогичен алгоритму, рассмотренному в 1-м параграфе. Отличие состоит в том, что здесь вместо списка номеров числовых модулей [гі;І2І рассматривается список, включающий как числовые, так и полиномиальные модули. Один отрезок задает номера модулей одной переменной или номера числовых модулей.
Вначале вычислений создается список отрезков intervals = {[І.тпі],..., [l,rrit], [1, /і]} полиномиальных и числовых модулей. Начиная с отрезка номеров числовых модулей [1,/г] и спускаясь по бинарному дереву, перемещаемся влево по списку отрезков intervals и делим эти отрезки до тех пор, пока в них останется один номер модуля или не останется свободных процессоров.
Эффективность для проведенных экспериментов находится в пределах от 30% до 95%. При увеличении количества процессоров ускорение вычислений уменьшается. Это связано с тем, что распараллеливание становится не выгодным и вычисления на граничном уровне требуют меньше времени, чем один шаг подъема по дереву алгоритма. Время на шаг подъема можно сократить, если все вычисления выполнять па граничном уровне, а при подъеме только передавать данные. Такой алгоритм рассматривается в следующем параграфе.
В 3-м параграфе описывается параллельный алгоритм вычисления характеристических полиномов матриц для кольца целых чисел и кольца полиномов с восстановлением, на листовых вершинах. За каждой листовой вершиной закрепляется некоторое число простых модулей, по которым происходит вычисление характеристических полипомов. Кроме этого за каждой листовой вершиной закрепляется множество коэффициентов характеристического полинома, которое будет восстанавливаться па этой вершине.
Алгоритм Леверье-Фаддеева
На этапе 1 достаточно считать только последнюю строку матрицы (Аг)ь. затем ее умножать на матрицу Аг, а при t — п — умножать лишь на последний столбец матрицы Аг. Поэтому необходимо выполнить Уг=і Y t=2г2 = 1/37т.4 + 1/6/73 — 1/Зп2 — 1/бп операций умножения, Ylr=i 21=2 r(r 1) — 1/Зп4 — 1/Зтг3 — 1/Зп2 + 1/Зп операций сложения. На остальных этапах количество кольцевых операций составит 0(п3). Поэтому алгоритм требует выполнения 1/377 + О(п3) операций умножения и столько же операций сложения в кольце R.
В основе алгоритма Сейфуллина [8, 26] лежит простой факт: правый нижний элемент матрицы Gt(x), которая является присоединенной для матрицы х Et — At, — это характеристический полином Xt-i = Ер=о ft-\xt l P матри-цы, получаемой вычеркиванием из матрицы At последней строки и последнего столбца:
Квазитреугольной называется матрица, у которой а] = 0 при г j + 1, т.е. равны нулю все элементы, расположенные ниже "второй" диагонали: {а\, a\i ., dn-\\- У квазитреугольных матриц характеристический полином вычисляется просто.
В основе алгоритма лежит вычисление квазитреугольной матрицы: сначала вычисляется квазитреугольная матрица Аи = DL lAL, а затем вычисляется характеристический полином данной матрицы det(xD — Ли)/ detD.
При вычислении квазитреугольной матрицы на шаге t (t = 1,..., п — 2) вычисляется матрица, у которой обнуляются элементы t-ro столбца под "второй" диагональю. При этом все вычисления происходят в исходном кольце коэффициентов, и все деления являются точными. где начальное значение d = 1, xD — Аи = (#]), i,j = l,...,n. Эта формула получается простым разложением определителя по последнему столбцу, dl обозначает определитель подматрицы порядка г, стоящей в левом верхнем углу.
Найдем оценку сложности алгоритма в числе кольцевых операций. На этапе 1 требуется выполнить jyfl ?(2(n)(n-l)+n(n)) = 7/6n3 + 0(n2) операций умножения, YH ii71 - t)(n — t — Ї) = l/3n3 + 0(n2) операций сокращения и YA=i((n)(n- 1) +n(n - t - 1)) = 5/6?i3 + 0(n2) операций сложения. На этапе 2 требуется выполнить 1/бп3 + 0(п2) операций умножения, п операций сокращения и 1/6п3 + 0(п2) операций сложении. Всего 4/Зп3 + 0(п2) операций умножения, 1/Зп3 + 0(п2) операций сокращения и п3 + 0(п2) операций сложения в области R.
Данный алгоритм является развитием предыдущего алгоритма. В основе алгоритма также лежит разложение данной матрицы А в произведение квазитреугольной В и диагональной D l матриц: А — BD l.
Вычисление матриц В и D происходит за п — 2 шага. На каждом шаге раньше выполнялось два матричных умножения и умножение на матрицу D }L, которое сводилось к выполнению {n — t)2 операций сокращения. Однако, умножение на матрицу D [\ можно на каждом шаге не выполнять. Но в конце вычислений нужно использовать новую диагональную матрицу, которая получается произведением всех матриц D [\. Для того, чтобы матрицы L/, Li и Dt остались прежние, нужно на каждом шаге вычислять те же, что и раньше, элементы а1 и Vі, используя для этого n — t операций сокращения.
Найдем оценку сложности алгоритма. На t-м шаге алгоритма вычисляется матрица и при этом выполняется (n — t — l){n — t)+ п(п — І) сложений и вычитаний, 2(n — t — l)(n — t)+ п(п - і) умножений ип — t делений. Поэтому асимптотические сложности операций при вычислении матрицы ?[П-Ч следующие: требуется выполнить 5/6п3 + 0(п2) операций сложения и вычитания, 7/6та3 + 0(та2) операций умножения и 1/2п2 операций деления. При нахождении матрицы D необходимо выполнить та — 2 операции умножения. На этапе 2 требуется выполнить 1/6та3 + 0(та2) операций сложения и вычитания, 1/6п3 + 0(та2) операций умножения и та операций деления. Всего п3 + 0(та2) аддитивных операций и 4/Зта3 + 0(та2) операций умножения и 0(п2) операций сокращения в области R.
Были рассмотрены 6 алгоритмов точного вычисления характеристического полинома матриц: метод Леверье [4], метод Леверье-Фаддеева [6], метод Чистова [23], алгоритм Берковича [24], алгоритм Сейфуллина [8], алгоритм Малашонка [10]. 2. Был предложен новый алгоритм [11] точного вычисления характеристического полинома, являющийся развитием алгоритма Малашонка.
Для кольца целых чисел вычисляются выражения для сложности алгоритмов в числе мультипликативных операций над машинными словами. Для метода Лсвсрьс, метода Леверье-Вииограда, метода Леверье-Фаддеева, алгоритма Чистова, алгоритма Берковича и алгоритма Сейфуллина выражения для сложности являются полиномиальной функцией, а для алгоритма Малашопка и нового алгоритма — экспоненциальной функцией. Эта оценка показывает эффективность прямых вычислений в кольце целых чисел. Экспериментально сравниваются алгоритмы, имеющие полиномиальную оценку. Экспериментально сравнивается лучший из прямых алгоритмов с лучшим алгоритмом, основанным на методе гомоморфных образов [29]. Даются рекомендации по применению алгоритмов вычисления характеристического полинома в кольце целых чисел.
Для кольца полиномов с целыми коэффициентами Z[.Ti,..., xt] описывается применение метода гомоморфных образов [29] к алгоритмам вычисления характеристических полиномов матриц. Находится верхняя оценка коэффициентов характеристического полинома, которая необходима для определения числовых и полиномиальных модулей. Найденная оценка обобщается для кольца полиномов от многих переменных.
Вычисление характеристических полиномов полиномиальных матриц
Следовательно, сложность этого алгоритма описывается экспоненциальной функцией (2.13). Отметим, что все предыдущие алгоритмы имели полиномиальную сложность, поэтому данный алгоритм является худшим из них при использовании стандартной арифметики в целых числах. Новый алгоритм [11]. Алгоритм [11] является видоизменением алгоритма Малашонка. Основное отличие заключается в том, что в алгоритме [11] при вычислении матриц А ь\ t = 1,..., п — 1, не выполняется умножение на матрицу Dj\, т.е. отсутствует сокращение элементов матрицы А$. Следовательно, в алгоритме [11] промежуточные результаты растут не меньше, чем в алгоритме Малашонка. Количество умножений слов для данного алгоритма также описывается экспоненциальной функцией. Полученные выражения числа машинных операций умножения сведем в таблицу. Метод Число машинных операций умножения для Znxn
Сравнивая выражения для числа машинных операций умножения в правом столбце таблицы 2, видим, что среди рассмотренных алгоритмов асимптотически лучшими являются методы Леверье, Леверье-Винограда и Леверье-Фаддеева. Их время вычисления растет как - {к + рп)п . Время вычисления ближайшего к ним алгоритма — алгоритма Сейфуллина растет как (/с + /?п)п5. Методы Леверье будут быстрее алгоритма Сейфуллина, если (/с + Лг)п4 81 jfr(k + (Рп)п5, т.е. для п 5100/19 « 4700. Поэтому для матриц небольших размеров лучшим среди прямых алгоритмов будет алгоритм Сейфуллина, а при п 4700 его будут обгонять алгоритмы Леверье, если в них использовать умножение по Штрассепу.
Обозначим через А = (а -) матрицу, полученную при /с — 1 шаге. Рассмотрим матрицу Sk, которая получается из единичной матрицы 1п заменой (к + 1)-го столбца на к-ът столбец матрицы А к\ Получаем алгоритм Данилевского [13]: В алгоритме предполагается, что все промежуточные системы векторов действительно являются базисами. Если на некотором шаге к система векторов получилась линейно-зависима, то матрица А имеет вид А к = где матрица А\ имеет форму Фробениуса. Тогда характе А[к) С ристический полином матрицы А равен произведению характеристических полиномов матриц А\ и А2 . Далее следует выполнять процесс приведения к форме Фробениуса матрицы А2 .
Найдем оценку сложности алгоритма в числе операций над элементами матрицы. На каждом шаге к = 1,... ,п — 1 надо сначала найти S 1 А к\ затем {S A) Sk.
При умножении Skl-A выполняется умножение п строк из Sk на п—к — 1 столбцов матрицы А к\ В к-ой строке матрицы Skl один элемент l/afc+i,fc+i в остальных по два: 1 и акк+1/ак+1 ft+1, г ф к + 1. Тогда требуется выполнить (п — 1) + (п — 1){п — к — 1) операций умножения, 2{п — 1)(п — к— 1) операций сложения и 1 деление. При умножении (S A) St выполняется умножение п строк из (SklA), в каждой из которых по п — к элементов, на к-ъш столбец матрицы Sk- Тогда требуется выполнить п(п — к — 1) операций умножения, п(п — к — 1) + к — 1 операций сложения. Всего в алгоритме требуется выполнить п3 — 5/2п2 + 3/2п операций умножения, п3 — 5/2n2 -f 7/2п — 2 операций сложения и п — 1 операцию деления в поле i . Затем восстановим коэффициенты полиномов fi(x),..., Д(#) по числовым модулям Pi,...,Pk в полином F{x), который является характеристическим полиномом данной матрицы А.
Для применения метода гомоморфных образов необходимо сначала определить наибольший коэффициент характеристического полинома. А затем выбрать необходимые простые модули. Лучшая известная сегодня оценка для наибольшего по абсолютной величине коэффициента характеристического полинома получена в работе [32]. Согласно этой оценке количество двоичных разрядов в наибольшем коэффициенте характеристического полинома не превышает где п — порядок матрицы, b — максимальное число двоичных разрядов у элементов данной матрицы.
Массив простых чисел предполагается заданным. Выбирая из пего последовательно простые числа и вычисляя их произведение, нетрудно выбрать достаточное для вычисления характеристического полинома данной матрицы количество простых модулей h. Требуется выполнение неравенства
Экспериментальное сравнение алгоритмов в кольце целых чисел Были проведены три серии экспериментов. В первой серии участвовали только те прямые алгоритмы, которые имеют полиномиальную оценку сложности в операциях над словами. Это алгоритмы Сейфуллина, Берковича, Чистова, Леверье-Вииограда и Леверье-Фаддеева.
Во второй серии участвовали алгоритмы, имеющие лучшие оценки по числу операций. Асимптотически лучшими среди прямых алгоритмов оказались алгоритмы Леверье. Но они начинают выигрывать у алгоритма Сейфуллина при п 4700.
Для больших п асимптотически лучшими будут алгоритмы, основанные па методе гомоморфных образов, в которых в конечном поле используются алгоритм Данилевского и новый алгоритм. Поэтому экспериментально сравним время вычислений алгоритмов, основанных на методе гомоморфных образов, и прямого алгоритма Сейфуллина.
В третьей серии сравнивался алгоритм, основанный на методе гомоморфных образов, в котором в конечном поле используется алгоритм Данилевского, с алгоритмами, реализованными в системах Mathematica 7.0 и Maple 9.5.
В первой серии участвовали прямые алгоритмы. Сравнивая коэффициенты при старших степенях к и п в выражениях для сложности в машинных словах (2.1), (2.2), (2.3), (2.4), (2.5) и (2.6), можно ожидать, что при вычислении характеристического полинома по алгоритму Сейфуллина результат будет получен быстрее, чем по алгоритму Берковича в 1.1 раза, — Чистова в 2 раза и для малых п быстрее, чем по алгоритмам Леверье и Леверье-Фаддеева в 5 раз.
Была проведена серия экспериментов, в которых вычислялся характеристический полином для целочисленных матриц, элементы которых содержат 50 бит. Размерность п матрицы менялась в пределах от 30 до 100. В таблице указано отношение времени вычисления характеристического полинома с помощью алгоритмов Берковича, Чистова, Леверье, Леверье-Фаддеева к времени вычисления алгоритма Сейфуллина, выраженное в процентах. n Алгоритм Берконича Алгоритм Чистова Метод Леверье-Винограда Метод Леверье-Фаддеева
Рассматривая алгоритмы для последовательной реализации алгоритмов вычисления характеристических полипомов целочисленных матриц, мы увидели, что среди прямых алгоритмов наилучшим будет алгоритм Сейфуллииа. Асимптотически лучшим из рассмотренных алгоритмов является алгоритм. основанный на методе гомоморфных образов, который в конечном поле использует алгоритм Данилевского, при этом он надежно обгоняет алгоритм Сейфулина, ко года порядок матрицы больше 35.
Алгоритм вычисления характеристического полинома полиномиальной матрицы
Эффективность для эксперимента 2 находится в пределах от 30 % до 95 %. При увеличении количества процессоров ускорение вычислений уменьшается и становится равным 1 для некоторого числа процессоров. Это связано с тем, что дальнейшее распараллеливание не выгодно и вычисления на граничном уровне требуют меньше времени, чем один шаг подъема по дереву алгоритма. Для данного эксперимента ускорение вычислений становится равным 1 для 256 процессоров. Время на шаг подъема можно сократить, если все вычисления выполнять на граничном уровне, а при подъеме только передавать данные. Такой алгоритм рассмотрим в следующем параграфе.
Пусть к — количество процессоров кластера с номерами 0, 1, 2,..., (к — 1) и на нулевом процессоре имеется исходная матрица А над полипомами из кольца Z[x\,.. ., xt]. Пусть множество М, которое содержит необходимый список простых чисел, имеется на каждом процессоре.
Параллельный алгоритм вычисления характеристического полинома матрицы состоит из четырех этапов.
Каждый процессор находит верхнюю оценку наибольшего по абсолютной величине числового коэффициента элементов характеристического полинома матрицы и верхние оценки наибольших степеней элементов характеристического полинома матрицы по каждой переменной. Для числовых матриц используются оценки, полученные в работе [15], для полиномиальных матриц оценки получены в параграфе 2.5.2.
Каждый процессор по найденным оценкам и заданному множеству числовых модулей М вычисляет необходимое для данной задачи количество числовых модулей и количество полиномиальных модулей по каждой переменной. В качестве полиномиальных модулей по переменной хг берём полиномы
В результате этапа 1 на каждом процессоре будет получена входная матрица, а также количество /г числовых модулей и количество 7?i-. .. ,mt полиномиальных модулей по каждой переменной.
Нулевой процессор разбивает один из полиномов на к частей, посылает полученный шаблон разбиения полинома на все процессоры (процедура MPI Beast). Процессор с номером 1, 2,..., (к — 1) получает от нулевого процессора шаблон разбиения полинома (процедура MPI Beast). Каждый процессор разбивает каждый из полученных полипомов па к частей в соответствии с шаблоном разбиения.
Таким образом на каждом процессоре будут получены остатки по всем модулям для всех коэффициентов соответствующей части характеристического полинома. Каждый процессор восстанавливает соответствующую часть характеристического полинома. При этом используется алгоритм Ньютона [29]. В результате на каждом процессоре будет получена соответствующая часть характеристического полинома.
Каждый процессор посылает свой результат нулевому процессору (процс-дура MPI Gather). Нулевой процессор получает полиномы от всех процессоров (процедура MPI Gather). Затем нулевой процессор объединяет полученные данные в искомый характеристический полипом матрицы. В результате на нулевом процессоре получен характеристический полином данной матрицы. Рассмотренный алгоритм даёт равномерную нагрузку па узлы кластера и обеспечивает хорошую масштабируемость.
Время вычисления характеристического полинома при использовании многопроцессорной вычислительной системы складывается из времени, необходимом для вычислений на листовых вершинах, и времени пересылки данных между процессорами. Докажем теоремы об оценке времени вычислений и оценке времени пересылки.
Теорема 3.1. Пусть А Є Znxn[.Ti,... :xt] — полиномиальная матрица, у элементов которой а — наибольший по абсолютной величине числовой коэффициент, s — наибольшее количество мономов, degj — наибольшая степень по переменной Х{ , і = 1,... :t. Пусть к — количество процессоров.
Тогда, время, необходимое для вычисления характеристического полиио-м.а матрицы А с использованием параллельного алгоритма с восстановлением на листьях, без учета времени пересылки данных меоіеду процессора ми равно
Время вычислений на каждом процессоре складывается из времени решения г задач в конечном поле, которое находится на этапе 2 (З.З.1.), и времени, необходимом для восстановления коэффициентов характеристического полинома, которое происходит на этапе 3 (З.З.1.). Время, необходимое для вычисления характеристического полинома целочисленной матрицы А Є Znxn на к процессорах с использованием параллельного алгоритма с восстановлением па листьях, равно Следствие 3.2. Пусть с помощью параллельного алгоритма (3.3.1.) для заданого размера матрицы П\ на к\ процессорах задача вычисляется за время Т. Тогда для матрицы размера п2 с аналогичными элементами задача вичислишся за тоже время Т на Теорема 3.2. Пусть А Є 1/іхп[хі,... ,xt] — полиномиальная матрица, у элементов которой а — наибольший по абсолютной величине числовой коэффициент, s — наибольшее количество мономов, degi — наибольшая степень по переменной Xj , г = 1,..., t. Пусть к — количество процессоров. Тогда время, необходимое для пересылки данных между процессорами при вычислении характеристического полинома с использованием параллельного алгоритма с восстановлением на листьях, равно Время, которое в алгоритме тратится на пересылку, складывается из времени TS\ рассылки исходной матрицы на все процессоры, которое выполняется на этапе 1 (З.З.1.), времени TS-j, обмена между процессорами частями полиномов на этапе 3 (3.3.1.) и времени TS сбора на пулевом процессоре фрагментов характеристического полинома от всех процессоров на этапе 4 (З.З.1.).
