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

РГ6 од

/ 8 ИЮН 199&ОССИЙСКАЯ АКАДЕМИЯ НАУК 1 ИНСТИТУТ СИСТЕМНОГО ПРОГРАММИРОВАНИЯ

На правах рукописи УДК 681.3.06

ТАР ЛАПАН Олег Анатольевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ОБЪЕКТНО-ОРИЕНТИРОВАННОГО

МАТРИЧНОГО ОБЕСПЕЧЕНИЯ

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

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

Москва -1998

Работа выполнена в Институте системного программирования Российской Академии Наук.

НА УЧНЫЙ РУКОВОДИТЕЛЬ:

Кандидат физико-математических наук Семенов Виталий Адольфович

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

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

Воеводин Владимир Валентинович

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

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

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Московский государственный авиационный институт

Защита состоится " 2.0" уауо\лХ 1998 г. в часов на заседании Специализированного совета Д.200.50.01 по защите диссертаций при Институте системного программирования РАН по адресу:

109004, Москва, ул. Б. Коммунистическая, д. 25.

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

Автореферат разослан " 2Л " ^ 1998 г.

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

Специализированного совета Д.200.50.01 кандидат физико-математических наук доцент

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

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

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

Роль объектных технологий в настоящий момент достаточно хорошо осознана. В последнее десятилетие ООП интенсивно используется при проектировании и создании операционных систем, сложных систем визуализации, баз данных. Значительно меньше внимания в этой области уделяется математическим библиотекам и системам, ориентированным на решение численных задач. До сих пор наиболее употребительным языком для вычислительных приложений считается Фортран. Многообразие математических библиотек, разрабатывавшихся на протяжении последних тридцати лет с применением процедурной технологии является одним из основных факторов, сдерживающих широкое использование объектных технологий при разработке математического программного обеспечения.

Принципы создания и особенности внутренней организации существующих сегодня математических библиотек и пакетов линейной алгебры (ЛА) отражают прежде всего их проблемную и методическую ориентацию. Так, пакеты ЬАРАСК, Ы№>АСК и ЕКРАСК реализуют прямые методы решения линейных систем и проблем собственных значений с плотными матрицами, пакет 1ТРАСК предназначен для решения линейных проблем итеративными методами, программы ЕЬЬРАСК ориентированы на работу со структурными матрицами, возникающими в результате разностной дискретизации эллиптических дифференциальных задач, возможности пакета БРАЯБРАК ограничены, главным образом, хаотически разреженными матрицами и т. п. Задание данных ограничений на тип матрицы и набор методов позволяет повысить эффективность решения поставленной задачи, но, в определенной степени, препятствуют дальнейшему развитию пакетов и библиотек и адаптации их к новым программным приложениям.

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

Результатом данной диссертационной работы является объектно-ориентированная математическая библиотека.

Целью работы является исследование возможностей применения ООП к программированию задач и методов линейной алгебры и разработка объектно-ориентированной математической библиотеки, допускающей работу с существенно различными матричными объектами при использовании широкого набора методов линейной алгебры. Главное внимание при проектировании библиотеки уделялось обеспечению ее широких инструментальных возможностей, обеспечивающих ее дальнейшее развитие и адаптацию к новым программным приложениям.

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

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

Разработка математической библиотеки классов отражает тенденции создания современного ПО на основе объектно-ориентированных технологий.

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

• проведен объектный анализ, в результате которого разработана объектная классификация векторов, общих, элементарных и специальных матриц, методов и алгоритмов JIA, допускающая непосредственные программные реализации;

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

• разработана и апробирована методика реализации векторных и матричных операций с использованием техники псевдоиндексного итерирования;

• разработана и апробирована методика унифицированной эффективной реализации пакета BLAS (Basic Linear Algebra Subroutines) в виде библиотеки шаблонов, инвариантной по отношению к различным форматам разреженности;

• предложена и реализована методика объектной реализация прямых методов ЛА в виде композиций матричных преобразований с использованием технологии элементарных матриц.

Практическая значимость работы состоит в возможности непосредственного использования реализованной матричной объектно-ориентированной библиотеки при разработке различных вычислительных приложений, а также в возможности использования предложенных и апробированных методик программирования при проектировании и разработке матричного ПО. Унифицированный дружественный интерфейс библиотеки и широкие инструментальные возможности существенно упрощают ее интеграцию с прикладными системами. Разработанная библиотека апробирована при проектировании и реализации интерактивной объектно-ориентированной математической системы и при создании рабочих прототипов объектно-ориентированных CAD/CAM систем.

Апробация работы. Проектирование и разработка библиотеки проводились в рамках проектов Российского фонда фундаментальных исследований и республиканской научно-технической программы "Информатизация России" Министерства науки Российской Федерации. Материалы диссертации докладывались на международной конференции "САПР" (г. Гурзуф, 1995), международной конференции "Новые информационные технологии в

науке, образовании и бизнесе" (г. Гурзуф, 1996), обсуждались на семинарах Института системного программирования РАН, Института прикладной математики им. М.В. Келдыша РАН, Научно-исследовательского вычислительного центра МГУ им. М.В. Ломоносова.

Публикации. По теме диссертации опубликовано 5 работ, тексты работ также доступны по сети Internet.

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

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

В первом разделе приведены общие принципы, используемые при разработке библиотеки. Данная работа - часть работы по созданию универсальной математической библиотеки общего назначения, проводившейся в Институте системного программирования РАН группой математического программного обеспечения. Универсальная библиотека предназначена для создания объектно-ориентированных программных приложений на языке С++, связанных с решением задач вычислительного характера.

Раздел JIA универсальной математической библиотеки представляет собой самодостаточную систематизированную библиотеку программных классов, выражающих ключевые понятия JIA и реализующих ее численные методы. Библиотека строится как единая иерархия наследуемых математических, проблемных и алгоритмических классов. При этом реализованные базовые классы следует рассматривать в качестве своеобразной инструментальной среды, которая может использоваться как для развития самой библиотеки, так и для создания программных приложений в различных предметных областях.

При разработке библиотеки не ставилась цель охватить наибольшее число вычислительных проблем и реализовать наиболее полный перечень численных методов JIA для их решения, что чрезвычайно сложно в рамках

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

В основу математической библиотеки JIA были положены следующие принципы:

• использование объектно-ориентированной методологии в качестве конструктивной основы для проектирования библиотеки,

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

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

• обеспечение высоких инструментальных возможностей библиотеки для унифицированного программирования новых классов векторных и матричных объектов, а также задач JIA и методов их решения,

• простота и удобство использования классов библиотеки при решении типовых задач стандартными методами J1A, наглядность интерфейса матричных и алгоритмических классов,

• надежность и эффективность вычислительных приложений, создаваемых инструментальным путем.

Во втором разделе описаны базовые классы универсальной математической библиотеки. Основной суперкласс Mathematics соответствует понятию абстрактного библиотечного объекта и реализует общесистемные функции: обеспечения доступа к математическим и машинно-зависимым константам, анализа и обработки ошибок, управления потоками ввода/вывода, сбора статистики и информационной помощи. Класс LinearAlgebra, наследуемый от базового суперкласса, имеет незначительное реальное наполнение, однако обеспечивает необходимую предметную систематизацию библиотеки.

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

Основными объектами библиотеки, с которыми связаны все ее методические построения, являются вектор и матрица. Унифицированная работа в рамках одного приложения с множеством разнотипных объектов достигается за счет разработки единых иерархий наследуемых векторных и матричных классов. В качестве основы таких иерархий предлагаются абстрактные суперклассы Vector и Matrix, выражающие наиболее общие свойства векторов и матриц и определяющие или реализующие их базовые операции и методы.

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

В качестве базовой основы для реализации раздела JIA предложен следующий уровень иерархии объектов JIA:

• LinearAlgebra

• Vector (Object)

• Matrix (Object)

• LinearSystem (Problem)

• LinearSystemAlgorithm (Algorithm)

• PivotingAlgorithm (Algorithm)

• StructuralAlgorithm (Algorithm)

• FactorizationAlgorithm (Algorithm)

Далее в разделе приводится описание классов иерархии и, в качестве примера проблемного класса, более подробно рассматривается класс LinearSystem, являющийся объектной интерпретацией математической системы линейных алгебраических уравнений.

Подобная организация раздела JIA, с одной стороны, является достаточно развернутой для построения дальнейших объектных классификаций на основе выделенных абстрактных типов данных, а с другой стороны, достаточно полно покрывает круг интересующих нас задач JIA. Кроме того, предлагаемая иерархия является открытой и позволяет легко расширять как

проблемный, так и алгоритмический репертуар библиотеки, например для

реализации проблем собственных значений и собственных векторов.

Особо отмечается, что представление объектов, проблем и методов их решения различными ветвями иерархии приводит к обобщенной реализации методов JIA, инвариантной по отношению к форматам используемых данных, и качественно меняет технологию разработки матричного обеспечения.

Вторая глава диссертации посвящена векторным и матричным классам библиотеки.

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

Конкретные классы векторов реализуют предлагаемый унифицированный интерфейс и отличаются, главным образом, способами организации структур данных. Иерархия классов векторов имеет вид:

• Vector

• DenseVector

* Vector2

• Vcctor3

» Vector4

» KandVevtor

« IndexVector

• List Vector

DenseVector реализует классическое представление плотного вектора в виде линейного числового массива заданной размерности. В случаях, когда плотно заполнен лишь какой-нибудь один сегмент вектора предпочтительнее применение класса ленточного вектора BandVector. Индексный вектор IndexVector хранит только ненулевые элементы и их индексы как плотные массивы. Наконец, списочный вектор ListVector хранит ненулевые элементы и их индексы в виде однонаправленного связного списка. Для более эффективной работы с векторами фиксированной низкой размерности, в частности в приложениях вычислительной геометрии, в библиотеку включены частные случаи реализации плотного вектора для размерностей 2, 3 и 4 - Vector2, Vector3 и Vector4.

Базовые методы классов, включая арифметические векторные операции и операции BLAS1, реализуются уже на абстрактном уровне с использованием виртуальных методов доступа к элементам. Существенно, что данные операции могут быть применены для произвольных векторных объектов. Для плотных и ленточных векторов реализация методов доступа к

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

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

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

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

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

Наконец, классы элементарных матриц, которые в данной работе отождествляются с различными матричными операциями: масштабированием, переупорядочением строк и столбцов, одноранговой модификацией, преобразованиями Хаусхолдера, Гивенса, Якоби, совсем не связаны с постанов-

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

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

• Matrix

• GeneralMatrix

• NonSymmetricMatrix

• SpecialNonSymmetricMatrix

• SymmetricMatrix

• SpecialSymmetricMatrix

• ElementaryMatrix

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

В трех следующих подразделах более подробно рассматриваются следующие абстрактные уровни матричной иерархии.

Матрицы общего вида GeneralMatrix являются основными матричными объектами, определяющими постановку большинства задач линейной алгебры. Далее в работе выделяется базовый набор матричных методов и приводится пример интерфейса абстрактного класса несимметричных матриц общего вида NonSymmetricMatrix. Основные матричные операции реализуются на абстрактном уровне с использованием виртуальных методов доступа к элементам. При этом допустимо переопределение основных операций на нижних уровнях с учетом структурных, специальных и программных особенностей частных матричных объектов. Заметим, что подобная организация программ не препятствует реализации машинно-зависимых версий операций BLAS для конкретных матричных форматов. Как и для векторных классов, отмечается недостаточная эффективность реализации методов доступа к элементам для разреженных форматов матриц и намечаются перспективы решения данной проблемы за счет использования механизма итерирования.

Далее в подразделе рассматриваются вопросы организации самостоятельной иерархии конкретных матричных классов с вершиной в GeneralMatrix. Данная иерархия объединяет наиболее распространенные виды матричных форматов, а также определяет место для возможных новых видов. Ниже приводится сокращенная, за счет векторно-организованных

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

• GeneralMatrix

• NonSymmetricMatrix

• DenseFilllnMatrix

• DenseMatrix

• Matrix2

• Matrix3

• Matrix4

• BandFilllnMatrix

• BandMatrix

» TriDiagonalMatrix

• LowerTriangularMatrix

• UpperTriangularMatrix

• UpperHessenbergMatrix

• BlockFilllnMatrix

• ChaoticFilllnMatrix

• CoordinatcMatrix

• RowMatrix

• ColumnMatrix

• KnutMatrix

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

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

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

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

Заключительный подраздел посвящен классификации элементарных матричных классов. В нем отмечается, что методы линейной алгебры в конечном счете редуцируются к сравнительно небольшому набору элементарных матричных преобразований. Применение ООП позволяет представить данные преобразования как матричные операции с объектами особого рода - классами элементарных матриц. С этой целью в разработанной матричной классификации выделяется особая группа элементарных матричных классов, объединяемая абстрактным классом ElementaryMatrix, а для объектов основных матричных классов определяются необходимые арифметические операции с элементарными матрицами. Разработка прямых методов решения систем линейных алгебраических уравнений (СЛАУ) выявила следующий необходимый набор элементарных матриц, представленный единой иерархией матричных классов:

• ElementaryMatrix

• IdentityMatrix

• DiagonalMatrix

о ScalingMatrix

• PermutationMatrix

» TranspositionMatrix

9 MultiRankModificationMatrix

• FrobeniusMatrix

* FrobeniusCoIumnMatrix

• FrobeniusColumnUpMatrix

• FrobeniusColumnDownMatrLx

• FrobeniusRowMatrix

• FrobeniusRowLeftMatrix

• FrobeniusRowRightMatrix

» OrthogonalElementaryMatrix

' HousekolderMatrix

• GivensRotationMatrix

• JacobiRotationMatrix

Данная иерархия включает следующие классы: единичной матрицы IdentityMatrix, диагональной матрицы DiagonalMatrix, выполняющей преобразования масштабирования, матрицы масштабирования отдельной строки или столбца ScalingMatrix, матрицы перестановки PermutationMatrix, соответствующий преобразованиям переупорядочения столбцов и строк, элементарной матрицы перестановок TranspositionMatrix, для перестановки двух столбцов или двух строк.

Особое внимание в подразделе уделяется семейству элементарных матриц Фробениуса ГгоЬепшМШгЬс - матриц единичного ранга, предста-вимых формулой: Е = I+х х уг, где I-единичная матрица, х и у - два ненулевых вектора-столбца. Данная матрица осуществляет одноранговую матричную модификацию и часто используется в прямых методах линейной алгебры. Например, столбцовая матрица Фробениуса используется в столбцовом алгоритме метода Гаусса-Жордана, нижняя столбцовая матрица — в столбцовом алгоритме Ш-факторизации. Кроме того, в иерархию включен класс МиШЛапкМоШАсайопММгЬс, определяющий группу многоранговых матричных преобразований, однако в реализованной версии библиотеки классы многоранговых преобразований не поддерживаются.

Важную группу элементарных матриц составляют ортогональные элементарные матрицы, объединенные в иерархии абстрактным классом OrthogonalElementaryMaírix. Конкретные матричные классы Ноияе/юШегМШгис, ауепзКо1аНопМШгЬс, 1асоЫ11о(аНопМШгЬс определяют преобразование Хаусхолдера, преобразования вращения Гивенса и Якоби соответственно.

Отмечается, что представленная классификация элементарных матриц определяет минимальный базовый набор матричных преобразований, используемых в линейной алгебре. Для более экономичной работы с памятью и эффективной организации вычислений предлагается использовать специальный контейнерный класс ММг'исСотроэШоп, который может представлять композиции тех или иных элементарных преобразований, а также использовать технологию создания контейнерных элементарных матричных классов, использующих для хранения необходимых матричных преобразований память основной матрицы и являющихся определенным объектным аналогом технологии т-р1асе.

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

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

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

Предлагаемый базовый набор из четырех векторных классов поддерживает различные формы регулярной и хаотической разреженности и может

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

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

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

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

// последовательное сканирование элементов вектора

for (Index 1=0; i<vector. Dimension О ; i++) vector[i]*=scalar;

// сканирование ненулевых элементов вектора

for (ListVectorlterator i(vector); i<vector.Dimension(); i++) vector[i]*=scalar;

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

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

• автоматическая поддержка уровня разреженности,

• высокая эффективность работы с разреженными операндами,

• инвариантность технологии программирования (буквально: текста программы) по отношению к различным классам разреженных векторов.

Организация классов векторных итераторов в иерархию, параллельную иерархии векторных классов, позволяет более эффективно программировать векторные операции на абстрактном уровне.

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

Использование псевдоиндексного итератора позволило упростить и унифицировать разработку программ, реализующих алгебраические операции над разреженными объектами.

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

В первом подразделе описывается идея и история создания пакета BLAS, как набора процедур, наиболее часто используемых при реализации методов линейной алгебры. Описывается его расслоение на три базовых уровня в зависимости от мощности операций, приводится состав пакетов BLAS1 и BLAS2.

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

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

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

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

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

кретными структурами данных. Приводимые далее результаты временного тестирования подтверждают это.

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

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

Для сравнения эффективности применяемых подходов к реализации матричного обеспечения были рассмотрены различные варианты реализации операций BLAS: специализированная реализация, ориентированная на конкретные матричные представления; универсальные реализации, основанные на использовании обычных индексов как методов элементного доступа для конкретных и абстрактных матричных классов; реализация при помощи матричных итераторов для конкретных классов. Далее в разделе приведены конкретные фрагменты кода, соответствующие каждой реализации, и описан характер тестовых матриц.

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

Способ реализации заполненная матрица в плагном строчном формате заполненная матрица в формате Кнута ленточная матрица в формате Кнута

Спец. реализация 4,12 5,82 0,49

Индекс (абстр.) 9,61 391,29 11,21

Индекс (конкр.) 8,56 385,96 9,83

Итератор 5,1 5,82 0,55

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

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

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

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

а LincarAigebra

» PivotingAlgorithm » StructuralAlgorithm

• FactorizationAlgorithm

• LinearSystemAlgorithm

• DirectLinearSystemA Igorithm

* ExplicULinearSystemAlgorUhm

• FactorizationLinearSystemAlgorithm

• llerativeLinearSystemAlgorithm

• EigenProblemAlgorithm » LeastSquaresAlgorithm

На приведенной в разделе иерархии все алгоритмы библиотечного раздела LinearAlgebra классифицируются на вспомогательные алгоритмы поиска главного элемента PivotingAlgorithm, структурные алгоритмы StructuralAlgorithm, алгоритмы матричной факторизации FactorizationAlgorithm, а также основные алгоритмы решения линейных систем LinearSystemAlgorithm, проблем собственных значений

EigenProЫemAlgorithm и задач о наименьших квадратах Ееах&циагеьА^огШхт. Алгоритмы решения линейных систем делятся на прямые и итерационные, что отражено в иерархии введением отдельных классов В1гес(Ипеаг8уь1етА^огШт, ИегаймеипеатБувЫтА^огШип. Прямые алгоритмы в свою очередь подразделяются на алгоритмы непосредственного решения систем ЕхрИсиЫпеаг5у51етА^огиИт и алгоритмы РагЛопгайопЫпеагБу51етА^огШт, использующие предварительную матричную факторизацию того или иного вида.

Далее в разделе кратко рассматривается тема объектной реализации итерационных методов линейной алгебры. Отмечается, что данный вопрос достаточно детально проработан в работах, связанных с проектированием библиотеки ШЬ++. Далее в разделе приводится возможная иерархия алгоритмических классов итерационных алгоритмов и отмечается естественность применения большинства принципов ООП к этой ветви иерархии.

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

Ключевой идеей при программировании прямых методов является представление их в виде композиции элементарных или сложных матричных преобразований: Г(А) = ^ х Г2х...А...хГ4_, х^, которые необходимо применить к исходной задаче для приведения ее к виду, допускающему непосредственное решение или упрощающему его. Далее в разделе описывается абстрактный класс ЫпеагА^еЬгаЫтеМА^огикт, наследуемый от базового класса ОиеОА^огШт, который реализует описанные выше методы проведения вычислений. Выделяется базовый набор операций, необходимых для такой реализации, приводится интерфейс класса. Описывается методика порождения конкретных классов прямых методов путем конкретизации типов и способов конструирования преобразований, участвующих в композиции.

Еще одному аспекту реализации прямых методов линейной алгебры -разработке класса композиции элементарных матричных преобразований посвящен следующий раздел. Класс Ма1г\хСотро$Шоп представляет собой гибкое средство для последовательного запоминания на каждом шаге алго-

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

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

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

» FactorizationAlgorithm

• NonSymmetricFactorizationAlgnrithm

• LUAlgorithm

» LURowUpAlgorithm

• LURowDownAlgorithm

• LUColumnUpAlgorithm

• LUColumnDownAlgorithm

• LDUAIgorithm

• GaussJordanAlgorithm

• OrthogonalFactorizationAlgorithm

• QRFactorizationAlgorithm

» HouseholdcrQRAlgorithm • GivensQRAIgorithm

• LQFactorizatioiiAlgorithm

• SymmetricFactorizationA Igorithm

• LL TCholeskyA Igorithm

• LDLTCholeskyAlgorithm

Вершиной данной иерархии является класс FactorizationAlgorithm, представляющий некоторый обобщенный алгоритм факторизации, а также

определяющий и частично реализующий его отдельные компоненты. Следующий уровень иерархии занимают классы ШпБуттеМсГааопъайопАи ¡>огШтх и БуттеМсРасЮпгайопА^огШчп, подразделяющие алгоритмы для несимметричных и симметричных матриц. Алгоритмы факторизации несимметричных матриц в свою очередь подразделяются на классы Ы1А1-цотИИт, юиА^огШт, Оатя^ЫапА^огШнп, ОгиюцопаШасШЬайопАI-I*огШип. Представленная иерархия охватывает основные направления алгоритмов факторизации и предоставляет богатые возможности ее дальнейшего развития.

Далее в разделе для каждого конкретного алгоритма приводится тип элементарной матрицы факторизации и ее математическое наполнение.

Заключительная пятая глава диссертации посвящена описанию инструментальных возможностей математической библиотеки. Инструментальный характер библиотеки является одним из основных качеств, выделяющих ее из ряда аналогичных библиотек, предоставляющих средства решения задач ЛА. Организация библиотеки в виде наследуемых иерархий объектных, методических и проблемных классов допускает ее дальнейшее эволюционное развитие как в направлении увеличения числа поддерживаемых векторных и матричных классов, так и в направлении расширения проблемно-алгоритмического репертуара за счет использования механизма наследования и перегрузки функций. Особо отметим, что следуя методикам разработки, предложенным в разделе методов ЛА, пользователь создает алгоритмы, инвариантные по отношению к используемым форматам данных, и все новые методы автоматически оказываются определены для всего многообразия уже реализованных матричных и векторных форматов.

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

В главе отмечается, что классы библиотеки выражают конкретные конструктивные понятия линейной алгебры: вектор, матрица, линейная система, алгоритм решения линейной системы... При этом интерфейсы классов, отражающие работу со свойствами выделенных объектов, по существу образуют высокоуровневую языковую среду, автоматически интегрируемую в

стандартные средства программирования. Использование данной среды заметно упрощает реализацию приложений и повышает их выразительность.

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

постановки и решения линейной системы уравнений:

// описательная часть LinearSystem Is;

NonSywmetricMatrix *matix;

Vector *x, *y;

PivotingAlgorihm *pivot_alg;

FactorizationAlgorithm * factorization_alg; LinearSystemAlgoritbm *solve_alg;

// пример конструирования матриц, Еекторсв, алгоритьшв поиска главного // элемента, факторизации и решения линейной системы: matrix= new'DenseMatrix(200,200) ; х = new DenseVector(200); у = new DneseVector(200);

pivot_alg = new PivotingAlgorihmAbsMaxElement; factorization_alg = new LUColumnDownAlgorithm; solve_alg = new FactorizationLinearSysteraAlgoritbm; //их инициализация

factorization_alg->Set(*pivot_alg> ;

solve_aig->Set(*factcrization_alg); Is.Set(»matrix); Is.Set (*y) ;

Is.Solve(*solve_alg, *x);

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

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

На основе приведенного выше примера программы можно наглядно проиллюстрировать это. Присваивая абстрактным указателям адреса конкретных алгоритмических объектов, можно проследить следующую цепочку: линейная система абстрактный алгоритм решения линейной системы <=> конкретный прямой алгоритм решения линейной системы методом факторизации ^ абстрактный метод факторизации конкретный метод столбцового Ьи-разложения <=> абстрактный метод поиска главного элемента конкретный метод поиска главного элемента по максимальному абсолютному значению в текущей подматрице. Манипуляции в рамках одной алгоритмической стратегии частными версиями алгоритмов решения линейной системы, факторизации и поиска главного элемента позволяют добиться равновысокой эффективности работы как с плотными, так и с разреженными матрицами. Например интерактивно меняя в приводимом примере тип конструируемой матрицы на матрицу Кнута, алгоритм поиска главного элемента на алгоритм, реализующий критерий Марковича, мы автоматически получаем стратегию решения линейной системы, учитывающую фактор разреженности.

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

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

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

Заключение содержит краткий перечень основных результатов работы.

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

разработанной на основе математической объектно-ориентированной библиотеки.

В заключение хотелось бы выразить благодарность моему непосредственному руководителю Семенову Виталию Адольфовичу - главному идейному вдохновителю данного проекта, Гайсаряну Сергею Суреновичу и Иванникову Виктору Петровичу - за общий стиль руководства и постоянную поддержку, маме - дорогой и любимой, а также товарищам по борьбе -Морозову Сергею Вячеславовичу и Ширяевой Екатерине Юрьевне.

Заключение

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

1. Спроектирована и реализована объектно-ориентированная математическая библиотека для решения задач JIA, включающая широкий ряд классов векторов, общих и элементарных матриц, методов и алгоритмов ЛА и сочетающая широкие инструментальные возможности с должным уровнем эффективности и мобильности. Библиотека также обладает богатыми потенциальными возможностями дальнейшего эволюционного развития.

2. Предложена методика унифицированной реализации матричных классов в виде шаблонов, параметризуемых типами векторов, для оперирования наиболее распространенными разреженными матричными форматами.

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

4. Предложена методика объектной реализация прямых методов ЛА как композиции матричных преобразований с использованием технологии элементарных матриц.

5. Намечены пути возможного развития библиотеки как в направлении увеличения числа поддерживаемых матричных форматов, так и в направлении расширения проблемного и алгоритмического репертуара.

Основные результаты диссертации опубликованы в следующих работах:

1. Семенов В.А., ТарлапанО.А. Технологии реализации разреженных матричных классов. // В сб. «Вопросы кибернетики. Приложения системного программирования» — М.: НСК РАН, 1995, с. 164-188.

2. Семенов В.А., Тарлапан O.A. Объектно-ориентированный подход к программированию прямых методов линейной алгебры. // В сб. «Вопросы кибернетики. Приложения системного программирования» — М.: ИСК РАН, 1996, с. 147-170.

3. Семенов В.А., Морозов C.B., Тарлапан O.A., Ширяева Е.Ю. Объектно-ориентированная среда для разработки вычислительных приложений. // Материалы XXIII международной конференции «Новые информационные технологии в науке, образовании и бизнесе», Украина, Крым, 15-24 мая 1996 г., с. 63-66.

4. Семенов В.А., Морозов C.B., Тарлапан O.A., Ширяева Е.Ю. Объектно-ориентированная инструментальная среда для разработки систем численного моделирования. // В сб. «Вопросы кибернетики. Приложения системного программирования» — M.: НСК РАН, 1997, с. 205-226.

5. Семенов В.А., Тарлапан O.A. Методика разработки библиотеки шаблонов BLAS для разреженных матриц. // В сб. «Вопросы кибернетики. Приложения системного программирования» — М.: НСК РАН, 1997, с. 227-239.