ПРОГРАММИРОВАНИЕ, 2012, No 2, с. 29-44
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
РЕШЕНИЕ БОЛЬШИХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, ВОЗНИКАЮЩИХ В ТЕОРИИ ИНТЕГРИРУЕМЫХ НЕАБЕЛЕВЫХ ЛОРАНОВСКИХ
ОДУ
© 2012 г. Т. Вольф1, Э. Шрюфер2, К. Вебстер1,
(1) Brock University,
Ст. Катарине, Онтарио, Канада,
(2) Бонн, Германия
E-mail: twolf@brocku.ca, eberhard.schruefer@ca-musings.de, kw07ty@brocku.ca
Поступила в редакцию 31.08.2011
В статье описывается пакет LSSS (Linear Selective Systems Solver) системы компьютерной алгебры Reduce, предназначенный для решения линейных алгебраических систем с рациональными коэффициентами. Данный пакет особенно эффективен при решении очень больших разреженных систем, имеющих решение, в котором многие переменные равны нулю. Описано применение пакета для исследования одного неабелевого лорановского ОДУ (обыкновенного дифференциального уравнения), недавно введенного М. Концевичем. Вычисления симметрий с помощью данного пакета подтверждают, что найденная ранее для этой системы пара Лакса порождает все первые интегралы по крайней мере до степени 14.
1. ВВЕДЕНИЕ
Многие задачи прикладной математики и других естественнонаучных областей приводят к решению разреженных линейных алгебраических систем. Так, при дискретизации непрерывных объектов соотношения между переменными, определенными в окрестности точки, обычно включают лишь малое число всех переменных; это число зависит от размерности моделируемых объектов, которая обычно мала.
В системах компьютерной алгебры имеются различные пакеты для решения разреженных линейных систем, например, пакет Р. Пирса [15], включенный в дистрибутив Maple 14: SolveTools:-Linear. Он автоматически применяется, если решается разреженная система.
Типичная проблема, возникающая при написании подобных пакетов для разреженных систем, заключается в возможно, неудачном выборе опорного элемента (pivot), что может увеличить количество переменных
в уравнениях и привести к неразреженной системе в процессе решения. Для многих систем этого невозможно избежать, но возможно отложить на последующие шаги. Например, при решении разреженной системы, получаемой из дискретизованного уравнения Лапласа (т.е. стационарного уравнения теплопроводности) ясно, что температура в каждой точке зависит от всех значений на границе и в типичной внутренней точке ненулевая.1
Изучаемые нами линейные системы также разреженные, но отличаются по своей природе. Значение большинства их неизвестных в полученном решении нулевые. Такие системы играют роль «селекторов» и названы в данной работе «селекторными системами», поскольку среди большого числа мономов (все они
1 Даже если температура на всей границе области нулевая, за исключением е-малой части, где она положительна, то температура во всех внутренних точках будет положительна.
имеют постоянные неизвестные коэффициенты) отбираются лишь некоторые линейные комбинации, удовлетворяющие определенным условиям; другие мономы отбрасываются, полагая коэффициенты при них нулями. Это резко отличает рассматриваемые нами системы от систем, возникающих из дискретизации уравнения Лапласа. В таблице 1 мы сравниваем оба класса систем.
Селекторные системы обладают многими полезными свойствами.
• Наличие нулевых неизвестных позволяет эффективно решать подобные системы пакетом LSSS, описываемым в нашей статье. LSSS работает в среде системы компьютерной алгебры Reduce ([8]).
• Из решаемой прикладной задачи обычно известно, принадлежит ли возникающая линейная система к этому классу, т.е. равны ли нулю большинство неизвестных. В этом случае и применима специализированная программа.
• Эффективность решения селекторных систем возрастает при увеличении сложности рассматриваемой задачи. Так, чем выше степень полиномиального анзаца при исследовании симметрий, тем больше размер линейной системы для неизвестных коэффициентов, но тем больше и процент нулевых коэффициентов и тем эффективнее методика решения, использующая этот факт (см. параграф 3).
• Подобные системы не только более эффективно решаемы; они могут быть более экономно сформулированы. Точнее, возможно сформулировать намного меньшие эквивалентные системы способом, описанным ниже в параграфе 3.7.
Стратегия использования нескольких методов решения систем уравнений и приписывания методам, реализующим наименее затратные и наименее рискованные (в смысле разрастания размеров промежуточных выражений) процедуры, наивысшего приоритета, не нова.
В команде solve системы Maple эта стратегия используется с 1985, вместе с эвристическим методом подстановки переменных, равных нулю, на начальных шагах
(см. [14]); в пакете Crack системы Reduce подобная стратегия совместно с приданием наивысшего приоритета подстановкам вместо неизвестных нуля применяется для решения переопределенных алгебраических и дифференциальных систем ([13]). Новизна подхода, предлагаемого в данной статье, проистекает из осознания того факта, что при обращении некоторых неизвестных переменных в ноль обычно многие другие переменные также зануляются, тем самым выгодно применять быстрые процедуры поиска и идентификации однотермовых уравнений для исключения соответствующих переменных и даже для того, чтобы избежать самого построения излишних уравнений.
Создание специализированного пакета для решения селекторных систем оправдано тем, что такие системы часто встречаются в приложениях, особенно при исследовании интегрируемости дифференциальных уравнений — при вычислении инфинитезимальных симметрий, законов сохранения, вариационных принципов или других качественных свойств, которые для большинства неинтегрируемых систем отсутствуют и для которых можно сформулировать подходящий анзац.
В следующем параграфе мы описываем одну прикладную задачу, приводящую к целой серии разреженных систем с высоким процентом зануляющихся переменных. Эта задача послужила отправной точкой при создании пакета LSSS. Читатель, интересующийся вычислительными аспектами формирования и решения разреженных систем, может перейти напрямую к параграфу 3, где описаны методы эффективного формирования и решения селекторных систем.
В параграфе 4 приведены времена решения систем, возникающих в описанной нами задаче. В следующем параграфе 5 обсуждаются некоторые важные для больших вычислений аспекты, связанные с реализацией пакета в системе Reduce. Параграфы 6 и 7 посвящены тестированию других систем компьютерной алгебры. Статья заканчивается списком имеющихся в пакете процедур в параграфе 8 и Резюме.
Таблица 1.
Характеризация двух типов разреженных линейных систем
Тип "численные" системы "селекторные" системы
примеры системы, получаемые дискрети- системы, получающиеся
зацией уравнений с частными при исследовании
производными (УЧП) симметрий УЧП
значения свободных любое вещественное 0 или 1
параметров в системе (граничные значения УЧП) (для выделения
линейных уравнений отдельных симметрий)
число нулевых практически нет большинство неизвестных
неизвестных в решении
разреженность системы да да
переопределенность нет да
применимость итерационных
схем для больших систем полезны бесполезны
данного типа
2. ПРИКЛАДНАЯ ЗАДАЧА
2.1. Неабелева система ОДУ
М. Концевич в своей программе построения некоммутативной алгебраической геометрии, вытекающей из запросов современной квантовой теории поля, предложил некоммутативную версию симплектической геометрии, в которой естественно появляются неабелевы системы ОДУ (обыкновенных дифференциальных уравнений) ([1]).
Точнее, он рассмотрел дискретное отображение
и ^ ит,-1 , V ^ и-1 + v-1u-1 (2.1)
([2]) и следующую неабелеву систему ОДУ, инвариантную при (2.1):
иг = т — т-1 -V-1, V = —vu+ vu-1+ и-1, (2.2)
где и, V — некоммутативные переменные (в частности, квадратные матрицы произвольного размера). В отличие от неабелевых систем ОДУ с полиномиальными правыми частями, исследовавшихся впервые в [3] и позднее в [4], [5], система (2.2) включает полиномы Лорана, т.е. полиномы от и, V и их обращений и-1^-1.
На основе численных экспериментов Кон-цевич предположил, что (2.2) сама является
интегрируемой. Это было недавно показано в [6], где была найдена пара Лакса, что также доказывает интегрируемость (2.1) (см. раздел 2 в [2]). Кроме того, в [6] был найден предгамильтонов оператор, отображающий первые «следовые» интегралы в инфините-зимальные симметрии. Наличие бесконечного числа симметрий или, еще лучше, пары Лакса, принимается в качестве критерия интегрируемости системы ОДУ или УЧП ([7]). Для проверки, что найденная пара Лакса позволяет построить все лорановские первые интегралы, мы вычисляем "грубой силой" все лорановские инфинитезимальные симметрии вплоть до некоторой степени и сравниваем полученный список с другим, полученным из пары Лакса. В настоящей статье мы описываем пакет ЬЯБЯ, созданный для решения линейных алгебраических систем, получающихся при вычислении всех таких симметрий до степени 16.
2.2. Симметрии Для заданной системы уравнений
и; = Р1(и,и,ьГ1,и-1), V = Р2 (и, V, и-1, V-1), (2.3)
в которой Р1, Р2 — полиномы от переменных и, V, и-1, V-1, лорановская (инфинитезимальная) симметрия определяется двумя полиномами
от и, V, и 1, V 1, такими, что поток
ит = (и, V, и-1, V-1), Vr = ф2(и, V, и-1, V-1)
(2.4)
коммутирует с системой, т.е.
БтБг и = БгБт и, (2.5а)
БтБг V = БгБг V. (2.5Ь)
Вектор (^1,^2)г называется генератором симметрии.
В данной статье система (2.3) генерируется,
исходя из (2.2). Полиномы ^1,^2 строятся
специальной процедурой, создающей наиболее
общие неоднородные полиномы (вплоть до
заданной степени) от некоммутативных пе-
11
ременных и, V, и 1, V 1 с символьными (абелевыми) коэффициентами Единственное условие, которое должно соблюдаться при построении ^1,^2, состоит в том, что и, и -1 и V, V 1 не должны стоять рядом, поскольку в таком случае произойдет их сокращение.
Условия симметричности по производным (2.5) должны удовлетворяться тождественно по и, V. Это означает, что после формирования условий (2.5), коэффициенты при всех различных произведениях степеней и, V, и 1, V -1 должны быть приравнены нулю
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.