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

ИНСТИТУТ ФИЗИКИ ВЫСОКИХ ЭНЕРГИЙ

92 - 61 На правах рукописи

Ларин Владислав Николаевич

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

05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Протвино 1992

М-24

Работа выполнена в Институте физики высоких энергий (г. Протвино).

Научные руководители: доктор физико-математических наук С.Н. Соколов, кандидат физико-математических наук С.Н. Грудцин.

Официальные оппоненты: доктор физико-математических наук C.B. Клименко, кандидат физико-математических наук В.П. Гердт.

Ведущая организация - НИИЯФ МГУ.

Защита диссертации состоится "_" _ 1992 г.

в _ часов на заседании специализированного Совета К 034.02.01

при Институте физики высоких энергий по адресу: 142284, Протвино Московской области.

С диссертацией можно ознакомиться в библиотеке ИФВЭ.

Автореферат разослан "_" _ 1992 г.

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

специализированного Совета К 034.02.01 С.А.Гумешок

© Институт физики высоких энергий, 1992.

Актуальность проблемы. Унификация п интеграция прикладного программного обеспечения - характерная черта современной компьютерной физики. Большое количество библиотек численных алгоритмов, систем компьютерной алгебры (СКА), графических пакетов, систем управления базами данных п т.д. свидетельствует о высоком уровне компьютеризации отдельных этапов физических исследований. Однако проблематичным остается совместное использование этих компонент в едином процессе научного исследования вследствие различия языков пх реализации, структуры и представления данных.

Как одно из решений этой проблемы^ в ИФВЭ был предложен проект интеграции программного обеспечения для физических исследований в рамках системы INTERCOMP. Она должна включать в себя интерпретируемый язык высокого уровня, средства для численного анализа, символьных преобразований, доступа к базам данных, визуализации информации (графики), эффективного диалога и т.д. Ориентация системы на обработку физической информации позволяет контролировать ее объем, а эффективность взаимодействия ее подсистем обеспечивается единым языком реализации (FORTRAN), выбор которого продиктован тем, что многие численные библиотеки реализованы на этом языке. Кроме того, к началу работ по созданию интегрированного комплекса (конец 70-х годов) FORTRAN был одним из самых распространенных языков программирования, что обеспечивало системе высокую мобильность.

С другой стороны, этот выбор делал невозможным использование в качестве подсистемы аналитических вычислений доступных СКА REDUCE (язык реализации - LISP) и SCHOONSCHIP (COMPASS). Пакет SAC-1 (FORTRAN) не имел специальных средств решения задач физики высоких энергий. Тем не менее, для достижения функциональной полноты интегрированной системы в ее состав должна входить подсистема компьютерной алгебры.

бильную, легко расширяемую систему проведения аналитических выкладок в области физики высоких энергий с последующим ее включением в интегрированную систему INTERCOMP; обеспечить производительность СКА на уровне системы SCHOONSCHIP, а ее программно реализованные возможности сделать более широкими; разработать входной язык, дающий возможность использовать СКА в автономном режиме; разработать методику проведения аналитических выкладок в физике высоких энергий с помощью созданной системы К А.

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

1. Разработка и реализация системы компьютерной алгебры НЕС AS (High Energy Computer Algebra System) для решения задач физики высоких энергий и смежных областей науки.

2. Создание специализированного языка управления преобразованием аналитических выражений на ЭВМ.

3. Реализация дуального (динамического - при хранении и статического - при обработке) представления выражений в памяти ЭВМ.

4. Реализация гибкого механизма управления выполнением подстановок с применением двух режимов их задания: однотабличного ("стандартного") и многотабличного.

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

а) алгоритма генерации полиномов большой длины, требующего времени O(JVlnN) и минимума дополнительной памяти;

б) алгоритма канонизации выражений, содержащих тензорные объекты с "немыми" индексами;

в) алгоритма обработки структурных констант группы SU(3) -распознавание "схем" свертки индексов и замена опознанных комбинаций более простыми, эквивалентными выражениями.

6. Методика проведения выкладок на языке HECAS в задаче вычисления сечений реакций 2—+3 в теории электрослабого взаимодействия.

Апробация работы. Основные результаты, представленные в диссертации, докладывались на III Всесоюзной конференции "Диалог человек -ЭВМ" [1], научном семинаре физического факультета МГУ "Символьные вычисления на ЭВМ", IV Международном совещании по аналитическим

Отдела математики и вычислительной техники и Отдела теоретической физики (ИФВЭ), Лаборатории вычислительной техники и автоматизации (ОИЯИ), в ЦЕРН'е, опубликованы в трудах Международного симпозиума по символьным и алгебраическим вычислениям ISSAC'91 [3] и работах [4,5,6]. В 1988 г. работа "Система аналитических вычислений НЕС AS" отмечена I премией на конкурсе научных работ ИФВЭ.

Структура диссертации. Диссертация состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 191 работу. Общий объем диссертации 151 страница, включая 21 рисунок и 1 таблицу.

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

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

В первой главе анализируется современное состояние программного обеспечения компьютерной алгебры. Рассматривается классификация систем компьютерной алгебры по назначению, согласно которой все СКА делятся на три класса: специализированные, общего назначения и универсальные. Анализ современного "парка" систем компьютерной алгебры позволяет ввести еще два класса: узкоспециализированные и интегрированные СКА. Первые ориентированы на решение определенной задачи в конкретной научной области (CAB КАПГООР). Вторые подразумевают интеграцию с численно-графическим программным обеспечением (системы MAPLE и MATHEMATICA).

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

Раздел 1.3 посвящен компьютеризации физических исследований и той роли, которая отводится в этом процессе системам КА. Сейчас СКА используются в основном для проведения рутинных аналитических выкладок. Однако появилась тенденция к их интеллектуализации, что вместе

сферу их применения (вычислительные эксперименты, доказательство теорем, экспертные оценкп п т.д.). Указывается на возможность создания банка общематематических знаний и банка теоретических моделей физики частиц на основе универсальной и специализированной СКА соответственно. Их объединение с существующими банками экспериментальных данных физики частиц под управлением интеллектуального интерфейса позволит в перспективе создать Базу Знаний Физики Частиц.

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

Обсуждаются две специфические проблемы КА: "разбухание" аналитических выражений и "бесконечная точность", в основе решения которых лежит, как правило, компромисс между быстродействием системы и ее запросами на память. Высказывается мысль о том, что языком реализации системы КА может быть практически любой язык программирования высокого уровня. Сейчас существуют п успешно эксплуатируются СКА, реализованные на различных диалектах LISP, языках PASCAL, FORTRAN, С, MODULA и др. Недостающие возможности некоторых из них (например, удобная работа с символами и структурами данных) реализуются как программные расширения языка.

В разделе 1.5 обсуждаются специфика цели и требования, предъявляемые к HECAS, как к подспстеме интегрированного комплекса. Одно из них - использование языка FORTRAN - следствие того, что на нем реализована базовая система для физиков. Подсистема разрабатывалась так, чтобы ее можно было использовать и как самостоятельную СКА, ориентированную на решение задач физики высоких энергии. Изначально заложенная возможность использования системы HECAS в двух режимах (автономном и под управлением INTERCOMP) является ее уникальной особенностью. Однако в диссертации она рассматривается как самостоятельная система.

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

ные физические задачи.

В разделе 2.1 определяются базовые понятия языка HECAS. Алфавит; числовые данные; имена объектов; моном - цепочка объектов, разделенных пробелами пли знаками умножения (*) и деления (/); выражение - цепочка мономов, разделенных знаками + или —; связанные и свободные подвыражения - как "объекты" выражений; операция присваивания М = Е, где М - одпн или несколько объектов, Е - произвольное выражение.

Команды описываются в разделе 2.2. Они имеют формат

$NAME parameter(s);

где $ - признак, a NAME - имя команды, за которым, после пробела, могут следовать одпн или несколько параметров (числа, объекты, выражения) и делятся на четыре группы. Приводятся примеры команд.

1. Команды - описатели объявляют имена рабочих объектов.

SMOM d P1,V,...; описывает векторы размерности d с именами PI, V,...; (/>1 (¿=4) и определяет пх модули МР1, MV,... (Здесь и далее в скобках даны подразумеваемые значения числовых параметров).

$TENS d T1,TENS,...; описывает несимметричные тензоры ранга d с именами Tl, TENS,...; 0<rf<16 {d=2).

Системный объект "^i" со свойствами мнимой единицы позволяет вводить комплексные выражения: Z=A+#*B.

2. Команды - операции.

$DIVIDE P,Q,QUOT,REST; - команда, по которой выполняется деление полинома Р на полином Q (полиномы от одной переменной). QUOT - полином - частное от деления, REST - полином - остаток.

3. Команды управления обработкой выражений.

$SPUR п; - устанавливает моду вычисления следов от выражений с 7-матрпцами. Параметр п имеет значения: 0 - следы не вычисляются, (1) - следы вычисляются только от 7-линий без бпспинорных амплитуд, 2 - вычисляются также следы от 7-линий с бпспинорными амплитудами.

SGRCOMM п; устанавливает правила коммутации для коварп-антных производных. При п=0 (исходная мода) производные не коммутируют, при п=(1) коммутатор равен нулю: [Va,Vt]=0, при п=2: [Va, УЬ]Ф;;1... = -($xjk...Rfab + $ixk...Rjab + ■••)) гДе ~ Произвольное

выражение с 4-индексами, R*ab - тензор Римана.

t. ломаноы управления выводим ши^иршщии.

SDENOUT п; - управление плотным выводом результатов вычислений. п—0 - вывод "один моном - на строку"; (1) - то же, но связанные подвыражения выводятся построчно; 2 - выражения целиком выводятся построчно (80 символов на строку).

В разделе 2.3 рассматриваются синтаксические правила представления объектов. В 2.3.1 представлены типы числовых данных: целые (—2), десятичные (3.14) и рациональные (31/7). Числа имеют ограниченную точность. Так, на ЭВМ ICL-1906A целые не могут превышать 1024. Если этот предел превышен, число преобразуется к десятичному виду.

В 2.3.2 рассматриваются скалярные переменные и полиномы. Их синтаксис совпадает, но семантика различна, что проявляется при их описании (первые вводятся описателем $VAR х,у; вторые - как левая часть операции присваивания Р=х+у;) и в результатах их обработки. Поскольку свободные полиномы подставляются, они отсутствуют в выходных выражениях. Переменные, напротив, могут присутствовать в них.

Подраздел 2.3.3 посвящен функциям п операции дифференцирования. В языке HECAS определены элементарные функции (SIN(x), ACOS(x), LN(x) и т.д.) и функции дифференцирования: D', D2', D3', D4'. Цифра указывает число переменных дифференцирования, а его порядок задается степенью соответствующей переменной. Последним аргументом такой функции является дифференцируемое выражение. Используются также произвольные функции, вводимые описателем $FUN. Результат дифференцирования таких функций содержит производные по их аргументам, которым присваиваются имена ARG1, ARG2,... Приводится пример вычисления второй производной от функции f(x,y), у—х'1.

$VAR х; $FUN 2 f; $UDIF; DF = D'(x"2,f(x,x~2));

DF = D'(ARGl"2,i(x,x"2)) + 2 D'(ARG2,f(x,x"2))

+ 4 x D2'(ARGl,ARG2,f(x,x~2)) + 4 x"2 D'(ARG2*2,f(x,x"2));

где ARG1 - первый (x), ARG2 - второй (x2) аргументы функции f.

Векторы ($M0M P,Q;) и индексы ($IND I,J;), обсуждаемые в 2.3.4, синтаксически эквивалентные объекты одного класса (ИНДЕКСЫ). Они используются только в контексте "скалярного произведения" (обозначается точкой) и в качестве "индексов" при тензорных объектах. Скалярное произведение векторов имеет вид P.Q, 1-ая компонента вектора Р - P.I, а метрический тензор - I. J. Непарные индексы можно рассматривать как единичные векторы (орты). Свертка по повторяющимся индексам

подразумевает суммирование, поэтому выражение г. 1 ц. ± преооразуется к виду P.CJ, скалярное произведение вектора самого на себя заменяется квадратом его модуля, свертка метрических тензоров - размерностью пространства (S'jSj=6'=dim).

В двух следующих подразделах описываются тензорные объекты, которые могут быть "внешними" (вводятся описателякш) и системными. Синтаксически - за именем тензора, после точки, следуют имена объектов из класса ИНДЕКСЫ, также разделенные точками. Пусть Т - тензор ранга 2 (имена индексов и векторов прежние), тогда допускается запись: T.I.J, T.P.Q. Последнее выражение является каноническим, представлением свертки тензора с векторами (P.I Q.J T.I.J). От такого представления можно отказаться, объявив векторы тензорами ранга 1. Так, если ввести тензоры $TENS 1 P,Q; структура выражения P.I Q.J T.I.J не изменится, но повторяющиеся индексы будут заменены системными: Р. I4A Q. I4B Т. I4A. I4B. Цифра указывает размерность системных индексов (подразумевается, что I.J - 4-индексы).

К системным относятся тензоры Леви-Чивиты (единичные полностью антисимметричные тензоры) с именем EPS; структурные константы группы SU(3) - два тензора: DLAM.a.b.c - симметричный и FLAM.а.Ь.с -антисимметричный (а,Ь,с - 8-индексы); тензоры кривизны, представленные тензорами Римана - RI4.a.b.c.d и Риччп - RI2.a.b; ковариантные производные, представленные девятью тензорами: G1', ..., G9' (число указывает ранг тензора), для которых выполнены отношения соответствия: Va <-► G1' .а, VaV6 <-+ G2' .а.Ь, ... Отличительной чертой этих тензоров является то, что вид их "симметрии" устанавливается с помощью команды $GRC0MM (у других тензоров он фиксирован).

В 2.3.7 обсуждается синтаксическая конструкция выражений, содержащих о-, 7- и А-матрпцы, системные имена которых соответственно ! и LAM. Векторный характер этих объектов определяет правило записи: Q.i, ! .р, LAM.a (для а- и 7-матрпц допускается запись: Qi, !р). Структурно выражения с объектами этих классов идентичны (назовем их "линиями"). Они состоят из цепочек соответствующих матриц, заключенных между двумя спстемнымп объектами, которые, обобщая, назовем "левым" и "правым" спинорами. Так, для 7-линий имеем:

U2.P !a !b...!с !5 U1.Q,

где Р, Q - 4-импульсы конкретной частицы, а,Ь,... ,с - 4-пндексы (и/или 4-векторы), !5 - матрица 75 и U2, U1 - левый и правый биспиноры, для которых (в моде $SPUR 2;) выполняется подстановка матриц плотности

^ui .г и^.г—т: 1 J lii , 1 ас ill — модуль исшила r J. и Jii '1 in. limit,

iследов от "чистых" 7-линий (без бпспинорных амплитуд) осуществляется ' при помощи функции GSP (! а ! b ...).

В следующем подразделе рассматриваются операции с матрицами (описатель $MATR). В системе выполняются сложение, умножение, возведение в целую степень, транспонирование (функция TRPS), эрмитово сопряжение (HETR), вычисление следа (SPUR), детерминанта (DET) и обратной матрицы (М"-1). Элементами матриц являются произвольные выражения, задаваемые следующим образом: MNAHE.m.n=expr; где MNAME - имя матрицы, m - номер строки, п - номер столбца.

В разделе 2.4 обсуждается важная компонента любой СКА - механизм задания подстановок. Синтаксически - это операция присваивания М=Е, где Е - произвольное выражение, а М - один или несколько ранее описанных объектов (не полиномов). Допускается "вырожденная" операция присваивания (без правой части), которая трактуется как отмена соответствующей подстановки. Предлагается новое решение задания обобщенных подстановок с использованием системных объектов ?Х, ?Y, ... (dummy-переменных) и ?А, ?В, ... ((fummy-индексов), которые заменяют громоздкую конструкцию "FOR ALL х,у,..., lhs(x,y,...)=rhs(x,y,...)". Подстановки этого типа позволяют в компактной форме определять даже рекурсивные функции, например, факториал:

$FUN F; F(?X)=?X*F(?X-1), F(l)=l; Р = F(15);

Р = 1307674368000; :: <-- Результат

Выполнением подстановок в однотабличном режиме (SUNISUB;) можно управлять командами SLASTSUB; устанавливающей порядок выполнения подстановок: "последняя задана - первая выполняется", и SADDSUB; устанавливающей режим накопления подстановок с одинаковой левой частью, а не замещения новыми подстановками старых, как в исходной моде ($ADDSUB OFF;).

Третья глада посвящена проблемам проектирования и реализации системы HECAS. Формулируются требования (решение задач физики высоких энергий, высокое быстродействие, развиваемость) и принципы реализации (независимость данных и алгоритмов, модульность, открытость). Приводятся данные по объему системы: тексты - 12 тыс. строк, объектный код: полная сборка - 300 Кбайт, неполная - 200 Кбайт. Система адаптировала на ЭВМ типа ICL, VAX, ЕС, IBM PC.

В разделе 3.1 рассматриваются классификация объектов и представление выражений в памяти ЭВМ. В системе используется дуальное

представление данных: статическое - при обработке, динамическое -при хранении. Первое реализовано для отдельных мономов (слагаемых) полиномиальных структур (ПС), которые, в свою очередь, имеют динамическое представление. В статическом представлении объекты монома занимают смежные ячейки массива целого типа - один код на ячейку (внутренним представлением объекта является целое число - "код"). Поэтому длина мономов ограничена размерностью массива (100 слов).

Динамическое представление выражений не имеет такого "искусственного" ограничения на число членов. Оно реализовано на базе пакета программ "для динамического распределения памяти и организации структуры данных" (WS-пакета)'и подразумевает, что на каждый моном отводится непрерывный "кусок" оперативной памяти ("банк"), в который помещаются числовой коэффициент (два двойных слова), "произведение" объектов в плотной упаковке (два кода на слово) и ссылка на следующий банк-моном. Таким образом, выражение представляется в виде цепочки банков, звенья которой связаны ссылками. Ссылка на головной банк ПС хранится в элементе массива JREF(pol), где pol - код соответствующего объекта типа ПОЛИНОМ. Такое представление выражений имеет структуру последовательного списка.

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

• дистрибутивное - скобки раскрыты: (аг—1)(х4-1) —► 1-х2, целые положительные степени вычислены: (х+1)2 —* 1+2х+х2;

• неполное - члены с нулевыми коэффициентами опущены: 1+2х3;

• лексикографически упорядоченное по возрастанию кодов и степеней: 1+х+ху+2ху2+х2+у+у'г, если переменные (в общем случае - объекты) заданы в следующем порядке $VAR х,у;

• упрощенное - подобные приведены, выполнены встроенные преобразования вида: x»xz х"+\ PXQ{ P-Q, Тцку Ткр и др.

• стандартизованное по повторяющимся индексам (замена "немых" индексов пользователя на системные).

В разделе 3.3 рассмотрена общая структура системы (рис. 1).

'Грудцин С.Н. - Препринт ИФВЭ 81-119, Серпухов, 1981.

\ BAN K~1 j MATRIX | 1 RATARI |

Блок Функциональных Модулей (БФМ) Рис. 1. Блочно-модульная структура СКА HECAS.

Здесь представлены отдельные модули: BANK - интерфейс с динамической памятью, RATARI - арифметический пакет п MATRIX - модуль обработки квадратных матриц. Ядро объединяет модули общего назначения (READ, WRITE, SORT и т.д.), а БФМ - модули обработки объектов конкретных классов (переменных, функций, тензоров п т.д.) ц выполнения отдельных операций (например, дифференцирования).

Раздел 3.4 посвящен описанию интерфейсных программ модуля BANK, назначением которых является реализация развязки между хранением и обработкой данных и выполнение операций с полиномами. Все обрабатывающие модули системы настроены на работу с отдельными мономами в статическом представлении (отрезками массива INTEGER V(100)). Поэтому система многократно обращается к банкам памяти через посредство подпрограмм модуля BANK. За одно обращение всегда передается один моном. Подпрограмма HCADD1(C,V(1),N,LP) создает банк, запаковывает в него моном (N слов массива V п коэффициент С) и вставляет его в упорядоченную полиномиальную структуру LP, приводя подобные. Подпрограмма JHCOPY(L,C,V(l),N) восстанавливает статическое представление монома, хранящегося в банке L.

В подпрограмме HCADD1 реализован алгоритм поиска со вставкой в упорядоченный список, требующий времени 0(п2), где п - число мономов в ПС. Для построения полиномов большой длины предложен алгоритм, реализованный в подпрограмме HCADD2(C,V(1),N,LB), который требует времени 0(п1пп). Параметр LB указывает на головной узел буферной структуры, который представляет собой банк с адресом LB, содержащий поля ссылок (LB-1, ..., LB-20) и данных (LB+1, ..., LB+20). В ячейках поля ссылок хранятся адреса головных банков буферов, а в соответствующих ячейках поля данных - счетчики их заполнения. Буфера - это цепочки упорядоченных между собой банков (мономов), длина которых

Блок Управления

(Ядро)

щ ограничена: п,■ < mах,-=тащ•/„■', где шах,- - максимальная длина буфера г'-го уровня, к> 1 - константа алгоритма, 0<i<?7aii—1 (¿/asi - номер буфера последнего уровня). Вставка мономов "по одному" осуществляется в небольшой список - буфер нулевого уровня. Когда он заполняется, его содержимое вливается в более крупный буфер следующего уровня. По заполнении последнего, его содержимое вливается в еще более крупный буфер и т.д. Слияние двух буферов с приведением подобных выполняется подпрограммой HCADD(L;,L,-+i). Когда все мономы переданы в буферную структуру, необходимо "довлить" содержимое промежуточных буферов в L,7asi и уничтожить саму структуру. Для этого служит подпрограмма HCEND2(LB). Выходным значением параметра LB является адрес головного банка ПС (L,/ast). При выбранных параметрах алгоритма тпахо=4, к=2, ilast=\9 и п^тах^ требуемое время 0(1.45-п(1пгг—0.7)). Предложенный алгоритм сходен с алгоритмом Неймана для сортировки массивов разбивкой на куски возрастающей длины, но требует меньше дополнительной памяти и исключает накладные расходы на копирование.

В разделе 3.5 описываются назначение модулей блока управления и некоторые алгоритмические решения, реализованные в них. Модуль READ предназначен для интерпретации входной информации, которая может иметь три контекста: предложения, которые начинаются с символа $, -команды, с буквы - операция присваивания, и двух двоеточий :: - комментарий. В первом случае считывается имя команды и по номеру элемента массива I<EY(52), в котором оно хранится, осуществляется переход на блок соответствующих операторов. Так, если введена команда-описатель, выполняется считывание имен объектов, следующих за ней, с занесением их в массив JNAMS основной (кодирующей) таблицы:

C0MM0N/CHCTAB/ N0B,N0B2,JNAMS(989),JDIM(989),JCLAS(989) +, JTYP(989), JREF(989),JREF3(989)

Кроме имени, объектам приписываются размерность, класс и тип (JDIM, JCLAS, JTYP). Переменная NOB - счетчик описанных постоянных объектов, NOB2 - счетчик временных полиномов. Эта таблица используется при трансляции выражений: имя^код, где код - номер элемента массива JNAMS, в котором хранится соответствующее имя, а также для обратной трансляции код—* имя - в модуле WRITE.

Одной из важнейших функций модуля READ является кодировка подстановок пользователя (lhs=expr, где Ihs - один или несколько описанных объектов). Для этого используются алгоритмы ссылок и табуляции, выбор

И

которых осуществляется по контексту. Первый используется для подстановок с простейшей Ihs вида var"n=expr, mom=mass, mom.?A—expr(?A), где п>О - целое число, ?А - dummy-вектор. При этом в элемент массива JREF(lhs) помещается код объекта из правой части. Такие подстановки реализуются в соответствующих функциональных модулях и имеют более высокий приоритет и эффективность, чем табулируемые подстановки. Второй алгоритм, используемый для широкого класса левых частей, более универсален и может работать в двух режимах: од-нотабличном ("стандартном") - "UT" (SUNISUB;) и многотабличном -"МТ" (SUNISUB OFF;). В системе используется семь таблиц: отдельно для скалярных произведений, функций, тензоров и "матриц плотности" (в трех классах спиноров) и общая таблица. Три первые таблицы используются только в МТ-режиме, остальные - в обоих режимах. В общую таблицу в МТ-моде помещаются подстановки с Ihs, состоящей только из произведений объектов, а в UT-моде - любые, кроме части ссылочных (yar~n=0, mom=mass) и "матриц плотности".

Все таблицы подстановок являются динамическими и структурно близки друг другу. Поэтому рассматривается некоторая "обобщенная" таблица, идентифицируемая следующим набором переменных: LQ - адрес банка - таблицы, NQ - текущее число занятых слов, NQMAX - текущее максимальное число слов в банке (при инициализации системы эти переменные имеют нулевые значения - таблицы отсутствуют), NQS -"шаг" расширения таблицы. Любая таблица создается при появлении первой подстановки соответствующего вида, которую, обобщая, можно представить так K1 К2.. .KN=C*N1"N2, где К - коды объектов из Ihs, С -числовой коэффициент, N1 - выражение, N2 - показатель степени. При этом создается банк из NQMAX—NQS слов. Если при заполнении таблицы NQ становится больше NQMAX, банк "расширяется" на величину NQS. Логическая структура таблицы подстановок приведена на рис. 2, где Ni—NKi+4 - поле г-ой подстановки.

N,

-"-• NQMAX

NK,

—-• 1

Nil - ■ - |Ci_i| N; I Kl;| •••• I KNil N1(1 N2;| C, I 0 I ••• I 0

NQ

Рис. 2. Логическая структура таблицы подстановок.

LQ

I

Недостатком метода табуляции является то, что при увеличении числа подстановок поиск их левых частей замедляет работу системы. Поэтому были приняты меры для повышения эффективности этой процедуры. В частности, используется упорядоченность объектов в левых частях подстановок и мономах, что продемонстрировано в диссертации при описании алгоритма реализации табличных подстановок. Предложенный многотабличный способ кодирования подстановок также повышает эффективность их реализации. Во-первых, каждая из "частных" таблиц заполняется, как правило, меньшим числом подстановок, чем общая. Во-вторых, поиск Ihs ведется соответствующими функциональными модулями, куда поступают объекты отдельных классов, а не в модуле ядра USUB (для общей таблицы), где сканируется весь моном. Результаты испытаний подтверждают эффективность принятых мер. Так, в МТ-режиме скорость выполнения подстановок (при равномерном заполнении таблиц) в 10 и более раз выше, чем в UT-режиме. Однако многотабличный способ кодировки менее гибок, т.к. подстановки из частных таблиц выполняются незавпсимо, что исключает возможность управления порядком их реализации за пределами конкретного класса Ihs. В UT-режпме порядком заполнения общей таблицы (а, следовательно, и порядком выполнения подстановок) можно управлять с помощью команд SLASTSUB и $ADDSUB.

Выражения, подаваемые на обработку, могут содержать ранее определенные полиномы, в том числе и свободные, которые немедленно подставляются. Эта операция (рекурсивная по своему характеру) - основная функция модуля PSUB, вызываемого модулем READ, сразу по окончании формирования текущего монома. Он извлекает по одному (с помощью JHCOPY) члены полиномов и вставляет их на "свои" места в новую последовательность кодов. Так формируется новый моном, который передается в модуль сортировки SORT. Его основными функциями является сортировка объектов монома по классам и передача отсортированных последовательностей объектов в соответствующие модули БФМ. Здесь при обработке объектов могут выполняться как встроенные, так и внешние подстановки. Кроме того, перед выходом из SORT, когда "отрезки" монома всех классов снова слиты в одну упорядоченную последовательность, вызывается модуль USUB, реализующий подстановки из общей таблицы. В результате, возвращаемый в PSUB моном может содержать "новые" свободные полиномы, которые также будут им подставляться.

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

женпй типа RimTlm. Предлагаемый метод обеспечивает эквива-

лентность подобных выражений в большинстве случаев и подразумевает замену немых индексов пользователя на системные индексы. В пределах одного монома каждая пара таких индексов заменяется парой индексов с уникальным именем (кодом) из стандартного набора - Id А, ИВ, ..., где d - размерность (генерируются при описании индексов размерности d).

Замена выполняется в порядке поступления (слева - направо) пар немых индексов, независимо от того являются они внешними или системными. Порядок пары фиксируется ее первым (левым) индексом. Пара, левый индекс которой оказался первым среди индексов, заменяется на первый индекс набора, вторая пара - на второй и т.д. Так, если два монома отличаются только именами немых индексов ($IND 4 i,j,l,m;):

... R.i.j T.i.j ... + ... R.l.m T.l.m ... ,

после стандартизации они станут тождественными:

...R.I4A.I4B T.I4A.I4B...+...R.I4A.I4B T.I4A.I4B...

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

Раздел 3.6 посвящен описанию арифметического пакета RATARI. Рассматривается представление числовых коэффициентов на уровне языка реализации системы, каковым является массив DOUBLE PRECISION С(2). Знак коэффициента определяется знаком С(1), тип - значением второго элемента: С(2)>0 - рациональная дробь, С(2)=0 - десятичная дробь. Поскольку представление целых чисел в вещественном формате двойной точности (без потери значащих цифр) ограничено, все арифметические программы контролируют величину элементов рациональных дробей по переменной DMAX, значение которой зависит от типа ЭВМ

(для ICL-1906A DMAX=1024). Если |С(1)| пли С(2) оказываются больше DMAX, коэффициент преобразуется к десятичному представлению: С(1)=С(1)/С(2), C(2)=0.D0. То же самое происходит, если операнды арифметических операций имеют различный тип. Однако все арифметические алгоритмы построены так, чтобы избежать преждевременного перехода к десятичному представлению. В основу здесь положен метод промежуточного сокращения на НОД. Один из алгоритмов, используемый в программе вычисления (Ai/A2)jV-(B1/B2), где ограничение особенно критично, рассматривается подробно. Было найдено два представления чисел типа Af/Bj, на базе которых построено и реализовано два алгоритма промежуточного сокращения на НОД. Их испытание указало на большую эффективность одного из них, который и был задействован в пакете. Кратко обсуждаются функции других подпрограмм пакета.

В разделе 3.7 обсуждается модуль обработки матриц - MATRIX. Основное внимание уделяется его статусу "надстройки" в иерархии системы и причине возникновения такого статуса. Более сложные связи функционального, по-сути, модуля с модулями ядра обусловлены спецификой матричных объектов, не имеющих в явном виде полиномиальной структуры, на обработку которой ориентирована система в целом. Поэтому модуль MATRIX, являясь "генератором" выражений, составленных из элементов матриц (полиномов), неизбежно становится промежуточным звеном между модулями READ и PSUB. Сформированные им выражения передаются на обработку в PSUB, который подставляет полиномы, и далее - по общей схеме (PSUB—»SORT—>БФМ). В заключение раздела приводится характеристика подпрограмм модуля, реализующих простейшие алгоритмы матричной алгебры: сложение, умножение, обращение, вычисление определителей и т.д.

В разделе 3.8 обсуждается блок функциональных модулей, который объединяет модули, выполняющие обработку объектов отдельных классов и некоторые операции. Управление в модули блока передается из модуля SORT. Однако не все из них имеют программную связь с этим модулем; они вызываются функциональными модулями, которые такую связь имеют. Кроме этой явной связи, между модулями БФМ существует и неявная связь, возникающая при обработке объектов определенных классов, в результате которой появляются объекты других классов, требующие иных обрабатывающих модулей. Важной функцией модулей блока является упрощение и упорядочивание объектов "своих" классов. В диссертации рассматриваются три важных с точки зрения назначения системы модуля (остальные одиннадцать описаны в приложении).

Модуль GAM предназначен для выполнения преобразований с цепочками 7-матриц Дирака, заключенных, возможно, в "биспинорные обкладки" ... щ): редукционных преобразований (в 4- и iV-мерном пространстве), подстановок матриц плотности, вычисления следов. Для выполнения последней операции использован алгоритм генерации полинома, составленного из "скалярных произведений" индексов при 7-матрицах, взятых по всем возможным перестановкам, который базируется на формуле редукции следа. (Здесь под "индексами" понимаются как собственно индексы, так и векторы). Цепочки с матрицей 75, если необходимо, редуцируются (в моде вычисления следа) с тем, чтобы могла быть применена формула Tr7a7J97i7£r75 = 4.i-eapsa-- В моде $SPUR 2; вычислению следа предшествует подстановка матриц плотности: upUp=jp+mp, где р и тр -4-импульс и масса конкретной частицы,

Встроенные подстановки, выполняемые в любой моде, реализуют простейшие редукционные формулы типа 7;г/'' = 4, 7,riV7'' = —27„ и т.д., а также тождества Чисхолма:

= ~2Ъ • • • 7a7i/J

нечетное

7//>7А • • • 7/)VY = 2(1<гЪ1\ ...Jp + Jp... 7a7i/7<T)-

четное

Переход к TV-мерному пространству (команда $DIMREG Ы;) инициирует выполнение редукционных преобразований вида

ЪГ = N, 7^7,7" = (2 - N)7„ ,

lulvlxY = 4(1/ • а) + (N - 4)7„7а ,

l^lvlxlpl^ = -^Iplxlv -(N- 4)ъъъ >

liTlvlxlplvl* = 1<Лр1\ЪЪ + lalulxlp) + (N - 4)71/7д7р7<г ■

Модуль LAM, предназначенный для выполнения преобразований с цепочками А-матриц Гелл-Манна, организован и имеет функции, аналогичные модулю GAM. Не отличается и управление работой этого модуля, реализуемое с помощью команды $LSPUR п; (п=0,1,2). В любой моде выполняются редукционные преобразования вида

А,А,- = A.AjAj = — |Aj, A;AjAt А,- = 4/у//,^тА/Ат — ^А^А*,

где fijk ~ антисимметричная структурная константа группы SU(3). Последняя формула является источником неявной связи модулей LAM и STRCON. В моде вычисления следа (п=1,2) выполняются подстановки

ТгА,- = 0, |ТгА;А;- = §6ij, |ТгА,А;А* = §(dijk + i ■ fijk),

где ¿¡¡к - симметричная константа 511(3). Если в А-линии больше трех матриц, реализуется редукционная формула: =

Модуль БТИСОК предназначен для обработки выражений с константами группы Би(3). В нем реализовано большое количество встроенных

упрощающих подстановок типа

~ 3&к1, = §¿4/, /¡1т/)п|/ьп = ~§/уЬ

в том числе для групп тензоров, свернутых по всем индексам, с числом констант N=2,4,6. Группы с нечетным числом антисимметричных констант заменяются нулем. Для 7У=2 числовые значения известны, а для N=4,6 были вычислены. Так, для N=4 получены следующие значения:

/цк/ит^ы/ктп = 36, <1{}кйцтйц „4тп = —20/3,

¿1]к<1цт}]Ы}ктп = 20, ¿у^/у^'/пЛгпп = —20.

Другие комбинации с N/=N¿=2 дают одно из двух последних значений. Шесть тензоров имеют две конфигурации свертки индексов, графически представленные на рис. 3 (численные значения приведены в диссертации).

/ к п V

\ 8 /

а)

б)

Рис. 3. Свертка индексов для шести структурных констант: а) симметричная, 6) несимметричная.

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

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

Четвертая глава посвящена обсуждению методики вычисления сечений реакций 2—»3 в электрослабом взаимодействии и имеет двоякую цель. Во-первых, дать представление о возможностях СКА НЕСАБ, которые могут расширяться как за счет накопления алгоритмов на уровне языка реализации, так и путем создания целевых пакетов НЕСАБ-программ. Во-вторых, представить вариант методики проведения выкладок с помощью системы в задаче расчета сечений на примере процессов

е+е~ —> , (1.а)

е+е~ —» ^ий. (1.Ь)

В разделе 4.1 рассматривается физический аспект задачи. Отмечается, что реакции (1) интересны с точки зрения изучения трехбозонных вершин (\VV\V, У=£,7), в процессе которого можно получить указания на составную природу \У- и £-бозонов. Трехбозонная вершина для процессов (1) представлена на рис. 4.

Выражение для нее содержит зависимость от двух феноменологических параметров к и А, связанных в случае (1.Ь) с магнитным и электрическим квадрупольным моментами 1У-бозона. В стандартной модели к—1, А=0,

но если IV и Z имеют составную природу, значения могут быть другими. В методических расчетах использовалась вершина с \у=0:

Уха0 = г ■ б ■ (ёа0(р+р')х + (1 + «„ХбаЛ?/? - К/?А?«)) (2)

и матричный элемент для диаграммы рис. 4 (случай рождения ^-бозона)

ё2 -Е"1* -Е0р А

м = ~еёг~8 [(р_ - ку - ад Крц. - к)2 - Щ\2 Уха0 *

х {у„{-к)1р(1 - т5)«е(-р+)) (о„(*;)7^(1 - 75)ие(р_)) . (3)

Наличие тензора У\ар и двух ¿-канальных пропагаторов делает задачу (даже при учете одной диаграммы и использовании высокоэнергетического предела р2__=р2+=к2=к2=0) сложной для вычисления "вручную".

В разделе 4.2 дается общая характеристика метода, который подразумевает разбивку расчета сечений на отдельные "шаги", каждому из которых соответствует "своя" НЕСАБ-программа (рис. 5).

Программа => Программа Программа

вычисления квадрата интегрирования разложения сечения

матричного элемента по фазовому по степеням

(вычисление шпуров) объему з/МЪ

и

Результат: Результат:

Ат/ап = щт„) ¿<т/Х1 = Дз/М^)

Рис. 5. Схема пакета НЕСАЭ-программ для вычисления сечений реакций типа (1).

Здесь 5 - квадрат полной энергии, М\у — масса И^-бозона, 1тп (т,п=0,1,2) - интегралы вида

_ г_6(Р-к- к)_<Рк<Рк

1тп ~ 1 [(р_ - к)* - М^[(р+ - ку - М&,}" 2Р 2А"' Р~р++р- 1'^

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

В разделе 4.3 обсуждается HECAS-программа вычисления квадрата матричного элемента (3). Приводится ее полный текст, указываются те незначительные изменения, которые трансформируют ее в программу для случая рождения фотона. Отмечается целесообразность вычисления квадрата амплитуды в два этапа - сначала выполнение заданных подстановок, а затем вычисление следа. В реальных задачах это увеличивает скорость вычислений в три и более раз. Фрагментарно приводится результат вычисления, а также время вычисления (20 с) и объем затребованной памяти (ПК слов) на ЭВМ ICL-1906A.

Раздел 4.4 посвящен программе интегрирования по фазовому объему. Это наиболее трудоемкая часть вычисления сечений. Так, в нашем случае предполагается вычисление "тензорных" интегралов вида

Jim.. _ Í 1; ¿Л k»kv\ ...б(Р-к-к) d4d4

Импульсы нейтринной пары, по которым выполняется интегрирование, содержатся в выражении для квадрата матричного элемента в виде скалярных произведений типа к), (р+-к), (p+-k)(q-k), (]>-■ к)(к-к) и т.п. Поскольку сложность интегралов (5) возрастает с увеличением степени пропагаторов и усложнением тензорной структуры в числителе подынтегральной функции, вычисление интегралов предварено блоком упрощающих подстановок, призванных снизить влияние этих факторов.

Система НЕС AS не имеет встроенного "интегратора", поэтому интегралы, вычисленные "руками", задавались подстановками, которые образуют "таблицу" из 27 тензорных интегралов, выраженных через 1тп (представлены в работе [5]). По завершении интегрирования, выражение упрощается с помощью блока "факторизующих" подстановок типа s_=(si2+si2)/2, s+=(si2-Si2)/2, где s_=(q-p-), s+=(q-p+). В диссертации представлен результат работы этой программы с выражением, полученным на предыдущем шаге, а также ее характеристики: число строк (без учета выражения для квадрата амплитуды) - 240, процессорное время -280 с, запрос на память - 70К слов.

В разделе 4.5 обсуждается программа разложения сечений по степеням s/Мцг. Причина ее включения в пакет - громоздкость ("некоммуникабельность") результатов, получаемых после интегрирования по фазовому объему. В случае рождения фотона, для которого применима процедура разложения, удается получить компактный результат, который можно использовать вплоть до энергий 100-120 ГэВ. Как иллюстрация, приводится результат вычисления сечения для процесса (l.b), с учетом всех

пяти диаграмм, в приближении первого порядка по степени Корот-

ко обсуждается результат, полученный позднее, с учетом членов второго порядка малости и параметра А? в выражении для вершины [6]. Решение этой задачи потребовало около 6.5 минут при исходной длине выражения (после интегрирования) более тысячи членов.

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

В заключение главы отмечается, что представленная методика, не претендуя на единственность, указывает путь расширения возможностей системы за счет создания пакетов НЕСАБ-программ, реализующих интегрирование, разложение по малому параметру, факторизацию.

В заключении сформулированы основные результаты диссертационной работы. Создание специализированной системы компьютерной алгебры НЕСАЭ стало возможным благодаря решению следующих задач:

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

2. Разработаны и реализованы подпрограммы, обеспечивающие дуальное представление выражений в памяти ЭВМ, включал алгоритм генерации полиномов большой длины, требующий времени 0(ЛЧпЛ^ и минимума дополнительной памяти.

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

4. Предложен и реализован способ канонизации тензорных структур с повторяющимися индексами - "метод стандартизации".

5. Реализована рациональная арифметика ограниченной точности.

6. Разработан и реализован базовый набор функциональных модулей для обработки объектов различной математической природы (функции, тензоры, сг-, 7-, А-матрпцы и т.д.) и выполнения операций (дифференцирование, нерелятпвпстское разложение).

7. Разработан вариант методики вычисления сечений реакций 2—»3 в электрослабом взаимодействии, включающий интегрирование по фазовому объему, разложение по малому параметру и факторизацию.

СПИСОК ЛИТЕРАТУРЫ

1. Грудцин С.Н., Ларин В.Н. Система аналитических вычислений НЕС AS// Материалы III всесоюзной конференции: Диалог человек-ЭВМ. - Серпухов, 1984. С. 201.

2. Grudtsin S.N., Larin V.N. HECAS-2: New version of the Computer Algebra System for High Energy Physics// Proc. of the IV International Conference on Computer Algebra in Physical Research. Abstracts - JINR Ell-90-204, Dubna, 1990. P. 23.

3. Grudtsin S.N., Larin V.N. Integrated System INTERCOMP and Computer Language for Physicists// Proc. of the 1991 International Symposium on Symbolic and Algebraic Computation. ISSAC'91 (Watt S.M., ed.) ACM Press, New York, 1991. P. 377-381.

4. Грудцин C.H., Ларин В.Н. Система аналитических вычислений HECAS. Описание входного языка. - Препринт ИФВЭ 87-2G, Серпухов, 1987. 52 С.

5. Ларин В.Н., Тихонин Ф.Ф. Пакет HECAS-программ для вычисления сечений реакций 2—>3 в теории электрослабых взаимодействий. -Препринт ИФВЭ 90-75, Протвино, 1990. 22 С.

6. Borisov G.V., Larin V.N., Tikhonin F.F. Testing the (WjW)-vertex in the process e+e~ —* / Z. Phys. С - Partical and Fields, v.41, 1988. P. 287-292.

Рукопись поступила 20 апреля 1992 г.