Метод построения блочно-малоранговой аппроксимации матрицы по её элементам тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

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

Михалев Александр Юрьевич

Метод построения блочно-малоранговой аппроксимации матрицы по её элементам

01.01.07 — Вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

11 ДЕК 2014

Москва 2014

005556609

005556609

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Московском государственном университете имени М.В.Ломоносова. Научный руководитель:

доцент Сколковского института науки и технологий, д.ф.-м.н. Оселедец Иван Валерьевич. Официальные оппоненты:

Самохин Александр Борисович, д.ф.-м.н., профессор. Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный технический университет радиотехники, электроники и автоматики", зав.кафедрой «Прикладная математика».

Смирнов Юрий Геннадьевич, д.ф.-м.н., профессор. Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Пензенский государственный университет", зав.кафедрой «Математика и суперкомпьютерное моделирование». Ведущая организация:

Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Защита состоится «30» декабря 2014 г. в 14:00 на заседании диссертационного совета Д 002.045.01 в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики Российский академии наук, расположенном по адресу: 119333, г. Москва, ул. Губкина, д. 8. С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики Российской академии наук. Автореферат разослан «_»_2014 г.

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

диссертационного совета Д 002.045.01 ¡у^.;^' /-/

доктор физико-математических наук Г. А. Бочаров

Общая характеристика работы

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

Основным результатом диссертационной работы является «мультизаря-довый» метод приближения блочно-малоранговых матриц, основанный на скелетных аппроксимациях не отдельных блоков, а их специальных объединений: блочных строк и блочных столбцов. Малоранговые аппроксимации блочных строк и блочных столбцов позволяют не только сократить используемую оперативную память, но и ускорить построение искомого малопараметрического представления по сравнению с мозаично-скелетным методом. Экономия времени и памяти становится возможной благодаря иерархии блочных строк и блочных столбцов: соответствующие блочным строкам и блочным столбцам базисные строки и базисные столбцы имеют рекурсивные зависимости. Полученное малопараметрическое представление в литературе обозначается как Н2-структура или ^-матрица и является алгебраическим аналогом быстрого мультипольного метода. Алгебраическая природа «мультизарядового» метода

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

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

Научная новизна. Введено понятие р-объёма прямоугольных матриц, которое совпадает с модулем определителя матрицы в случае 1-объёма. Приведена явная функция 2-объёма для прямоугольных матриц, обоснованы верхние оценки коэффициентов в /2-норме и построен «жадный» алгоритм поиска подматрицы максимального 2-объёма. Оценки псевдоскелетной аппроксимации матриц расширены на случай выбора разного количества базисных строк и столбцов. Разработан и опробован на двух задачах новый итерационный метод построения %2-аппроксимации матриц.

Практическая ценность. Разработанный в диссертации метод поиска подматриц максимального 2-объёма может быть использован для уменьшения погрешностей скелетных аппроксимаций, построения новых крестовых методов аппроксимации матриц и многомерных тензоров. Предлагаемый в работе «мультизарядовый» метод, в свою очередь, является удобным средством решения различных гиперсингулярных уравнений и может быть, например, использован для решения задач аэро- и гидродинамики методом дискретных вихрей. Для применения «мультизарядового» метода к решению задачи не нужно строить какие-либо аналитические ряды, в отличие от быстрого мультипольного метода.

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

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

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

Создан программный пакет h2tools, реализующий предложенные алгоритмы.

3. Проведено масштабное тестирование пакета h2tools на суперкомпьютере «Ломоносов» на задаче вычисления энергии десольватации на сетках с сотнями тысяч дискретных элементов. Получено ускорение в сотни раз по сравнению с программой DISOLV.

Апробация работы. Результаты диссертационной работы докладывались автором и обсуждались на научных семинарах НИВЦ МГУ, ИПМ РАН и на конферециях: 52-я научная конференция МФТИ (2009), 55-я научная конференция МФТИ (2012), трехсторонний франко-немецко-российский научный семинар «Разделение переменных и приложения» (2010), международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2011», научная конференция «Ломоносовские чтения-2011», научная конференция «Ломоносовские чтения-2012», научная конференция «Ломоносовские чтения-2013», научная конференция «Ломоносовские чтения-2014», международная суперкомпьютерная конференция «Научный сервис в сети Интернет: поиск новых решений» (2012), симпозиум «Биоинформатика и компьютерное конструирование лекарств» в рамках XXI Российского национального конгресса «Человек и лекарство» (2014).

Личный вклад. Результаты, описанные в главах 2 и 3: верхние оценки и алгоритм поиска подматриц максимального 2-объёма, оценки прямоугольной псевдоскелетной аппроксимации, итерационный «мультизарядовый» алгоритм и численные эксперименты — получены автором самостоятельно. Кроме этого, автору принадлежат результаты численных экспериментов с применением «мультизарядового» метода, описанные в главе 4.

Публикации. Основные результаты диссертационной работы опубликованы в 2 статьях: в статье в журнале, входящем в базу цитирования Web of Science [1], и в статье в журнале из перечня ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК [2]. В работе [1] Михалеву А.Ю. принадлежит основная идея метода, программа ЭВМ и численные эксперименты, Оселедцу И.В. принадлежит общая постановка задачи. Статья [2] опубликована в журнале из списка ВАК, автору диссертации принадлежат програм-

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

Объём и структура работы. Работа состоит из 105 страниц и содержит введение, 4 главы, заключение и список литературы. Список литературы включает 92 пункта.

Основное содержание работы

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

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

2. Вычисление локальных коэффициентов для приёмников взаимодействия по мультипольным коэффициентам. Эта операция обозначается M2L.

3. Иерархический пересчёт локальных коэффициентов в приёмники взаимодействия. Эта операция часто обозначается как L2L.

В первой главе приводятся необходимые предварительные сведения: скелетное разложение и различные оценки погрешности скелетной и псевдоскелетной аппроксимаций в чебышёвской и спектральной нормах, принцип максимального объёма, доминантные подматрицы, «жадный» алгоритм поиска доминантной подматрицы maxvol, мозаичное разбиение матрицы, мозаично-скелетная структура (которая в зарубежной литературе зачастую обозначается как К-структура или Н-матрица), блочные строки и блочные столбцы мозаичного разбиения с соответствующей Н2-структурой блочно-малоранговых мат-

риц. Так же, как и в быстром мультипольном методе, умножение "Н2-матрицы на вектор выполняется в 3 этапа:

1. М2М: рекурсивное вычисление коэффициентов, аналогичных «мульти-польным» коэффициентам,

2. M2L: вычисление коэффициентов, аналогичных «локальным» коэффициентам,

3. L2L: рекурсивный пересчёт коэффициентов, аналогичных «локальным» коэффициентам.

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

Вторая глава посвящена аппроксимационным свойствам прямоугольных подматриц. Основная задача здесь состоит в следующем: в матрице А найти такую подматрицу Я, чтобы элементы матрицы С, одного из решений уравнения А = СН, были как можно меньше. В первую очередь, это необходимо для минимизации ошибки аппроксимации матрицы А её базисными строками, если сама матрица А вычислена с погрешностью. Случай поиска квадратной подматрицы максимального 1-о&ьёма с соответствующими оценками приведён в первой главе. Очевидно, дополнительные степени свободы положительно сказываются на уменьшении различных норм матрицы С. К сожалению, определение 1-объёма как модуля определителя матрицы не применимо к прямоугольным матрицам. В разделе 2.1 сформулировано обобщённое понятие р-объёма матриц: р-объёмом матрицы Я е СА'ХГ будем называть объём множества G(H)P из следующего выражения:

G(H)P = {г; <Е Rr : Эс € ||с||р < 11 v = сН}.

Данное определение применимо как к квадратным, так и к прямоугольным матрицам и совпадает с модулем определителя в случае р = 1 для квадратных матриц. Рассмотрим сингулярное разложение матрицы Я = USV, U £ CKxh, S €

ШКхг, V е Сгхг. Очевидно, С(Я)2 = в (Б) 2, а С(5)2 представляет собой фигуру, ограниченную г-мерным эллипсом в А"-мерном пространстве, поэтому 2-объём матрицы Н есть произведение объёма шара, ограниченного единичной сферой в г-мерном пространстве, и всех сингулярных чисел матрицы Н. Таким образом, поиск подматрицы максимального 2-объёма среди всех подматриц размера К х г в матрице размера N х г можно свести к поиску подматрицы с максимальным произведением сингулярных чисел. В свою очередь, произведение сингулярных чисел легко вычислять по следующей формуле:

г

Дет* = л/сЫН'Н.

1=1

Поэтому поиск подматрицы максимального 2-объёма эквивалентен максимизации следующего функционала:

уо12(Я) = \/бе1П"П.

В разделе 2.1.1 сформулирован принцип максимального 2-объёма подматрицы: если подматрица обладает максимальным 2-объёмом среди всех подматриц размера К х г в матрице размера Лг х г, то существует такая матрица коэффициентов, что длина любой её строки ограничена сверху выражением \/к+1-г- Доказательство данного принципа следует из теоремы Бине-Коши об определителе произведения двух матриц. Произведение двух матриц А и В даёт квадратную матрицу порядка т, если матрица А имеет п столбцов и т строк, а матрица В имеет п строк и т столбцов.

Теорема Бине-Коши: Определитель матрицы АВ равен нулю, если п < т, и равен сумме попарных произведений соответствующих друг другу миноров порядка т, если п > т.

с!е1 (АВ) = ^ с!е1(Лг) с!е1(Д),

г

где с!е1(.4,) и сЫ( Д ) — соответствующие миноры.

Следствием данной теоремы является следующая лемма: Лемма: В рамках условия теоремы Бине-Коши, будем называть подматрицы соответствуюгцими, если они стоят в столбцах (матрицы А) и строках (матрицы В) с одинаковыми номерами. Тогда, если п > т, то определитель матри-11ы АВ равен одной (п — т)-ной суммы определителей попарных произведений

соответствующих подматриц размеров (п — 1) х т (подматрицы матрицы В) ит х (п — 1) (подматрицы матрицы А):

где Л; получается из А вырезанием 1-ого столбца, а В1 получается из В вырезанием {-ой строки.

Доказательство данной леммы приведено в тексте диссертации.

Если для данных матриц Л и Я существует матрица С такая, что А = СН, то матрица С = АН\ где Я' - псевдообратная к Н матрица, является решением системы А — СН в смысле наименьших квадратов. Тогда для любой строки Аг матрицы А с соответствующей строкой С, матрицы С верно следующее тождество на определители:

Предполагая, что Я — подматрица максимального 2-объёма среди всех подматриц размера К х г в матрице А, оцениваем левую часть последнего тождества при помощи леммы:

Заметим, что данный принцип максимального 2-объёма выполняется и для прямоугольных доминантных подматриц, определение которых дано в разделе 2.1.1.

Раздел 2.1.2 содержит описание жадного алгоритма поиска подматрицы максимального 2-объёма. Структура данного алгоритма походит на структуру алгоритма шэхуо1, описанного в главе 1: в матрице С находится строка с максимальной длиной, соответствующая ей строка из А приписывается к подматрице Н, увеличивая размер последней. Так как С = АН"1, где Н^ - псевдообратная к Н матрица, то при расширении Н необходимо лишь пересчитать её псевдообратную. Это можно сделать при помощи формулы Шермана-Вудбери-Моррисона. Если в матрицу Н добавляем г-ую строку матрицы Л, то:

!=1

Уг = 1..п : <1е1

= (1 + ||С4||2)СЫ(Я*Я).

Аналогичным образом вычисляются и длины строк новой матрицы С: Vj = I..N :

В Алгоритме 3 из раздела 2.1.2 формализована блок-схема соответствующего жадного алгоритма поиска подматрицы максимального 2-объёма.

В разделе 2.2 проведена работа по расширению существующих оценок псевдоскелетной аппроксимации А » CA^R, где С содержит базисные столбцы матрицы A, R содержит базисные строки матрицы А, а матрица А* - псевдообратная к подматрице на пересечении базисных строк и столбцов. Случай, когда количество столбцов матрицы С совпадает с количеством строк матрицы R, то есть когда А — квадратная подматрица, описан в главе 1. Многие оценки из главы 1 расширены на случай прямоугольной А, для этого введена функция tir, п, к), являющаяся расширением функции t{r, п) из работы (Горейнов, Тыр-тышников, Замарашкин, 1997). Пусть U - ортогональная матрица размера п х г. Обозначим через Mk{U) все подматрицы размера к х г. Определим t(r, п, к) по следующему правилу:

f(r, п, к) = —---т—-.

miny maxpg^fc/) amin{f)

Фактически, для любой ортогональной матрицы существует такая подматрица, что спектральная норма её псевдообратной не превосходит величину t(r, п, к). Расширенные оценки сформулированы в соответствующих теоремах: Теорема 2.2.1 (Точность т-псевдоскелетной аппроксимации) Пусть матрица А € <CNxM, такая что А = Z + F, rankZ = r, ||F||2 < е, имеет следующую блочную запись:

Гаи Ап

А —

An А22

Тогда существует т-псевдоскелетный аппроксимант А, построенный на подматрице An, такой что

Il А - Â||2 < е(4 + 2s + 3s2 + 2(1 + s)\/l + s2),

где s —максимальная из U-нормматриц Z-2iZ\1 и Z\XZ\2. Теорема 2.2.2 (Точность r-псевдоскелетной аппроксимации) Для любой матрицы А € СЛГхЛ/, такой что А = Z + F, rankZ = г, ||F||2 < с, существует

т-псевдоскелетный аппроксимант А, построенный на п строках и т столбцах, такой что

\\А - А\\2 < (5¿(г, ЛГ, пЩг, М, т) + 2Цг, ЛГ, п) + 2«(г, М, т) + 2)е.

Теорема 2.2.3 (Точность СОЯ-аппроксимации) Для любой матрицы А € Сл'хМ, такой что А = £ + .Р1, гапк£ = г, ||^||2 < е, существует СйЯ-аппроксимация А, построенная на п строках и т столбцах, такая что

\\А-А\\2 < {1+ + е.

Теорема 1.1 А Для любой матрицы А € Сл хМ, такой что А = 2 + ^ гапк.2 = г, || [| 2 < е, существует т-псевдоскелетный аппроксимант А, построенный на п строках и т столбцах, тп > п, такой что

\\А-А\\2< £¿(72, М, т) \Л+£2(г, И, п).

Третья глава содержит основную часть описания предлагаемого в диссертационной работе «мультизарядового» метода приближения блочно-малоранговых матриц при помощи Н2-матриц. Раздел 3.1 посвящен «муль-тизарядовому» представлению %2-матриц, основное отличие которого состоит в следующем: операция М2Ь состоит в умножении векторов на относительно небольшие подматрицы исходной матрицы. Такой подход позволяет хранить не сами матрицы операции М2Ь, а лишь номера соответствующих строк и столбцов, что приводит к сокращению на порядок памяти, необходимой для хранения Т^-матрицы. Частным случаем такого формата является модифицированное скелетное разложение:

А = С А'1 Я = сАя,

С = СЛ"1, Я = А_1Я,

где С - матрица из базисных столбцов матрицы А, Я — матрица из базисных строк матрицы А, а А - подматрица на пересечении базисных строк и столбцов. «Мультизарядовое» представление может быть вычислено при помощи

скелетной аппроксимации блочных строк и блочных столбцов. При этом полученные базисные строки и столбцы будут вложены друг в друга. В разделе 3.2 показано, что если для скелетных аппроксимаций использовать полные блочные строки и полные блочные столбцы, то сложность полученного метода для матриц размера N х М будет составлять 0{ЫМ) операций. Требование сокращения количества операций может быть удовлетворено выбором «хороших» подматриц: «хороших» строк для блочных столбцов и «хороших» столбцов для блочных строк. Если «хорошие» строки и столбцы даны заранее, то вычислить вложенные базисы блочных строк и блочных столбцов можно при помощи Алгоритма 4 из раздела 3.2. Однако любые практические задачи требуют адаптивного вычисления «хороших» строк и столбцов. В разделе 3.2.1 приведён пример адаптивного вычисления «хороших» наборов: «хорошие» строки блочного столбца делятся на «хорошие» строки блочного столбца, стоящего выше по иерархии, которые принимаются известными, и «хорошие» строки непосредственно самого блочного столбца, являющиеся базисными строками специальных блочных столбцов. Соответствующий метод вычисления базисных строк и столбцов сформулирован в Алгоритме 5. В случае, если базисные строки и столбцы известны, по ним можно вычислить «хорошие» наборы для блочных строк и столбцов, стоящих выше по иерархии. Данный подход описан в разделе 3.2.2 и соответствующем Алгоритме 6. Таким образом, получаем итерационный алгоритм: взять заданные «хорошие» наборы для блочных строк и столбцов, стоящих выше по иерархии, вычислить базисные строки и столбцы, пересчитать «хорошие» наборы по полученным базисным наборам. Инициализировать начальное приближение «хороших» наборов можно пустыми множествами строк и столбцов. Описание данного итерационного алгоритма приведено в разделе 3.3, в Алгоритме 7.

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

и максимальные значения времени (Рисунок 1) построения аппроксимации и памяти (Рисунок 2), необходимой для хранения матрицы в %2-формате, вычисленные с использованием 1 итерации «мультизарядового» метода по 100 различным случайным распределениям частиц внутри единичного куба [0,1]3.

(а) Максимальное значение (Ь) Среднее значение

Рис. 1: График зависимости времени построения аппроксимации от параметра точности т и количества частиц N.

(а) Максимальное значение (Ь) Среднее значение

Рис. 2: График зависимости памяти для хранения аппроксимации от параметра точности т и количества частиц N.

Задача вычисления энергии сольватации в рамках модели поляризуемого континуума сводится к решению системы линейных уравнений Ад = /, где элементы матрицы А вычисляются следующим образом:

( (е-1) ((г.-«Ч)-"1)$ ^ А д = I 4?1-(1+£) ' Т ■>

\ ш-Е^ИУ. * = 2

Структура %2-матриц подразумевает близость блочных строк и блочных столбцов к малоранговым матрицам. Аппроксимация именно этих строк и столбцов составляет основу «мультизарядового» метода. Для большого класса

задач блочные строки и столбцы соответствуют «дальнему взаимодействию». Представленная на следующих графиках погрешность меряется в спектральной норме относительно «дальнего взаимодействия», так как именно такие взаимодействия вычисляются приближённо (то же самое верно и для быстрых мультипольных методов). Отдельно стоит упомянуть зависимость точности от количества итераций «мультизарядового» метода: достижение погрешностей порядка 1СГ8 требует всего одну итерацию для задачи многих тел и две итерации для задачи вычисления энергии сольватации молекулы.

(а)

(Ь)

Рис. 3: Зависимость относительной погрешности приближения «дальнего взаимодействия» для задачи электростатики (слева, N = 100000) и задачи вычисления энергии сольватации (справа, N = 222762) от параметра точности

и количества итераций.

Четвёртая глава является последней главой и представляет результат применения «мультизарядового» метода приближения плотных матриц для ускорения вычисления энергий десольватаций различных молекул с лиганда-ми. Энергия десольватации описывается как энергия сольватации комплекса белок-лиганд за вычетом энергий сольватации белка и лиганда по отдельности и определяет энергию связывания белка с лигандом. Это оказывается полезным при компьютерной разработке лекарств, так как многие патологии связаны с функционированием белков и их активных центров. Блокировка таких белков-мишеней осуществляется путём связывания с их активными центрами относительно небольших молекул-ингибиторов. Чем точнее вычислена энергия десольватации, тем лучше можно спрогнозировать связь белка с лигандом. Достаточно высокая практическая предсказуемость достигается при погрешности расчёта энергии связывания белок-лиганд, не превосходящей 1

ккал/моль. В рамках численных экспериментов была использована континуальная модель растворителя (РСМ), которая приводит к необходимости решения систем линейных уравнений. Матрица системы при этом оказывается блочно-малоранговой и, более того, соответствующие блочные строки и столбцы могут быть приближены матрицами малых рангов с любой требуемой точностью. Поэтому оказывается возможным применение «мультизарядового» метода для приближения системы уравнений. На графике 4 представлены результаты сравнения 3-х программ:

1. МСВН: аппроксимация «дальних взаимодействий» матрицы «мультиза-рядовым» методом с погрешностью г = 1СП4, решение системы уравнений итерационным методом GMRES с погрешностью 10~4,

2. РСМ: решение системы уравнений с плотной матрицей при помощи од-ношагового итерационного процесса со специально подобранным шагом (метод РСМ из программы DISOLV),

3. SGB: Вычисление энергии десольватации с помощью эвристического метода Surface Generalised Born, реализованного в программе DISOLV. Погрешность превосходит требуемые 1 ккал/моль.

Сравнение проводилось на 22 различных комплексах белок-лиганд из базы данных PDB, каждая из перечисленных программ на вход получала одни и те же аппроксимации поверхностей молекул с шагом сетки 0.1 А, 0.2 Аи 0.3 А. Некоторые из поверхностных аппроксимаций достигали 550000 поверхностных элементов, при этом программа МСВН работала до 300 раз быстрее программы РСМ.

Заключение.

Диссертация посвящена блочно-малоранговым матрицам, возникающим при решении различных физических задач. Особое внимание уделено специальным блочно-малоранговым структурам: К- и %2-матрицам. «Мультизаря-довый» метод, являющийся основным результатом диссертации, представляет собой итерационный метод приближения блочно-малоранговых матриц 'Н1-матрицами в «мультизарядовом» формате. Количество итераций, необходимых

Рис. 4: Ускорение, достигнутое при использовании «мультизарядового» метода (МСВН), относительно программы РСМ на поверхностных сетках с шагами 0.1 Á, 0.2 Ä и 0.3 Á.

для приближения матрицы с требуемой точностью, зависит от поставленной задачи и составляет всего 1-2 итерации для представленных примеров. Неявным, но значимым преимуществом «мультизарядового» метода является количество элементов матрицы, которые необходимо вычислить для построения Н2-приближения: всего O(N) значений.

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

Статья в журнале Web of Science

1. Oseledets I.V., Mikhalev A.Yu. Representation of quasiseparable matrices using excluded sums and equivalent charges//Linear Algebra Appl. — 2012 . —Vol. 436, Issue 3 — P. 699-708.

Статья в журнале из списка ВАК

2. Михалев А.Ю., Офёркин И.В., Оселедец И.В., Сулимов A.B., Тыртышни-ков Е.Е., Сулимов В.Б. Применение мультизарядового приближения больших плотных матриц в рамках модели поляризуемого континуума для растворителя // Вычислительные методы и программирование. — 2014. — Т. 15. — с. 9-21.

Принято к публикации

3. Михалев А.Ю., Оселедец И.В. Прямоугольные подматрицы максимального объема и их вычисление // Доклады академии наук. — 2014.

Подписано н печать: 30.10.2014

Заказ № 10356 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 vvww.autoreferat.ru