Нелинейные аппроксимации матриц тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Оселедец Иван Валерьевич

Нелинейные аппроксимации матриц

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

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

Москва 2007

1615-?!

003161571

Работа выполнена в Институте вычислительной математики РАН Научный руководитель: член-корреспондент РАН, профессор Е Е. Тыртышников

Официальные оппоненты

доктор физико-математических наук, профессор А А Абрамов доктор физико-математических наук, А В Сетуха

Ведущая организация.

Московский государственный университет им М В. Ломоносова

Защита состоится « 14 » ноябуя 200 7 г в 15 часов на заседании диссертационного совета Д 002 045 01 в Институте вычислительной математики РАН по адресу 119333, г Москва, ул Губкина, д 8

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

Автореферат разослан « 10 » октябуя 200 7 г

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

диссертационного совета Д 002 045 01 доктор физико-математических наук

Г А Бочаров

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

Актуальность работы

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

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

Плотные матрицы описываются Т^2 параметрами Если мы хотим ускорить работу с ними, то необходимо построить «сжатое» представление матрицы с помощью меньшего числа параметров К сожалению, точные представления малым числом параметров доступны лишь для ограниченного числа случаев Например, это матрицы инвариантные относительно сдвига — теплицевы матрицы, или в многомерном случае многоуровневые теплицевы матрицы Однако если мы попытаемся выяснить структуру обратной матрицы к таким матрицам, то сразу обнаружим отсутствие явных формул, выражающих элементы обратной матрицы через элементы исходной простым и быстро вычислимым способом Поэтому надо искать такие малопараметрические представления, с которыми можно эффективно выполнять матричные операции, такие как обращение матриц и решение линейных систем

Обычно решение линейной системы происходит с использованием некоторого быстрого алгоритма матрично-векторного умножения и итерационного метода Для быстрой сходимости, как правило, требуется предобу-славливатель Построение хороших предобуславливателей — задача сложная, и обычно решается путем выбора из готового набора «стандартных» предобуславливателей, таких, например, как неполное Ш-разложение Однако их вычислительная сложность и «качество» (те скорость сходимости соответствующего итерационного метода) не всегда высоки Поэтому представляет интерес решение задачи о построении «наилучших» предобуславливателей и создании некоторого общего подхода к приближенному обращению структурированных матриц Обе задачи сводятся к задачам нелинейной аппроксимации матриц

Кроме обращения и предобуславливания плотных матриц при решении

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

Исследования, отраженные в диссертации, поддерживались грантами РФФИ №02-01-00590-а, 04-07-90336-в, 05-01-00721-а и 06-01-08052-офи

Цели работы

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

1. Создание быстрых методов построения наилучших циркулянтных преодобуславливателей на основе С + И аппроксимации и доказательство существование таких аппроксимаций в случае теплицевых матриц

2 Построение нестандартных вейвлет-пребразований, адаптированных к заданной неравномерной сетке

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

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

Методы исследования

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

для работы со структурированными матрицами Используются методы теории приближения рациональными функциями

Научная новизна работы

Предлагаемый в работе метод черных точек является новым и принадлежит автору На данный момент существующие аналогичные алгоритмы являются итерационными и об их глобальной сходимости ничего неизвестно Пред ложенный в диссертации алгоритм находит точное решение за конечное и небольшое число итераций Теоремы о существовании С + Я аппроксимаций к тешшцевым матрицам получены в соавторстве с Н Л Замарашкиным Общий подход к обращению структурированных матриц, теоремы о сходимости метода, использование матриц малого тензорного ранга со структурированными факторами для обращения матриц большого размера, возникающих из интегральных уравнений, являются новыми и принадлежат автору Также является новым и принадлежит автору супербыстрый алгоритм приближенного обращения двухуровневых теплицевых матриц Данный метод имеет сублинейную сложность, а все методы, имеющиеся в литературе, имеют существенно более высокую вычислительную сложность Также новыми являются полученные автором теоремы о структуре обратных матриц к матрицам малого тензорного ранга специального вида

Защищаемые положения

1 Метод черных точек для построения циркулянтных предобуславли-вателей и восстановления пропущенных элементов в больших массивах данных и теоремы о существовании С + И аппроксимаций для широкого класса теплицевых матриц

2 Построение вейвлет-преобразований, адаптированных для неравномерных сеток

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

4 Супер-быстрый алгоритм обращения двухуровневых теплицевых матриц сложности 0^^/rilog'xn) и теорема о структуре обратных матриц к матрицам малого тензорного ранга специального вида

Практическая значимость работы

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

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

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

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

Апробация работы

Основные результаты докладывались на различных конференциях на международных конференциях «Матричные методы и операторные уравнения» (ИВМ РАН, 2005 и 2007), на «Ломоносовских чтениях» (Москва, ВМиК МГУ, 2006 и 2007), на третьей международной конференции «Математические идеи П Л Чебышева и их приложение к современным проблемам естествознания» (Обнинск, ИАТЭ, 2006), на международных конференциях НАЭ-З-З (Амстердам, 2006) и 1ЬА8-14 (Шанхай, 2007), на международной конференции по структурированным матрицам (Гонконг, 2006), на «Тихоновских чтениях» (Москва, ВМиК МГУ, 2006 и 2007), на семинаре «Вычислительные и информационные технологии в математике» (научные руководители Ю М Нечепуренко, В И Лебедев, Е Е Тыртышни-ков), на семинаре мехмата МГУ (научный руководитель Б С Кашин)

Публикации

Основные результаты диссертации отражены в публикациях [1-6]

Структура и объём работы

Работа состоит из введения, основного текста и заключения Объем диссертации — 102 страницы Библиография включает в себя 66 наимено-

ваний Диссертация содержит 8 рисунков и 8 таблиц

Краткое содержание работы

Введение К решению линейных систем уравнений — основной задаче линейной алгебры и матричного анализа — сводится подавляющее большинство практических вычислительных задач В связи с ростом мощности вычислительной техники размер матриц в приложениях все время увеличивается Однако в приложениях требуется иметь дело с матрицами еще больших размеров, недоступных для современных суперкомпьютеров В частности, при решении интегральных уравнений, как известно, возникают линейные системы с плотными матрицами Если для решения использовать стандартный метод (такой, как метод Гаусса), то сложность решения составит операций, где N—число неизвестных Более то-

го, память на хранение всей матрицы при N ~ 500000 составляет порядка 2 Терабайт — такая память доступна сейчас лишь на параллельных машинах Например, при решении двумерной задачи на сетке с числом узлов по одному направлению 1000, размер матрицы сразу становится равным миллиону Означает ли это, что задачи такого размера не могут быть решены на рабочей станции7 Если речь идет о реализации известных алгоритмов на существующих компьютерах, то ответ положительный Однако новые вычислительные алгоритмы могут сделать возможным решение таких задач и на персональной станции Разработке таких алгоритмов и посвящена данная диссертация.

Плотные матрицы описываются 1М2 параметрами Если мы хотим ускорить работу с ними, то необходимо построить «сжатое» представление матрицы с помощью меньшего числа параметров Матрицы, описываемые малым числом параметров, будем называть структурированными

Часто структура матрицы видна сразу или следует из физических ; свойств задачи Например, в задачах с оператором, инвариантным относительно сдвига, получающиеся матрицы имеют теплицеву (или блочно-теплицеву в многомерных задачах) структуру, т е элемент матрицы зависит лишь от разности индексов ач — Ь1__5 Для теплицевых матриц существуют быстрые алгоритмы, основанные на БПФ Теплицевы матрицы — классический пример матриц с линейной структурой Можно привести другие примеры ганкелевы матрицы (ач = Ьг+,), ленточные матрицы, разреженные матрицы

Еще один важнейший класс матриц — матрицы, малого ранга, те матрицы вида

А = ИУТ,

И е Мпхт, V € Мтхт, где ранг г <с т,п Это — пример матрицы с нелинейной структурой ее элементы зависят от параметров (элементов матриц И и V) нелинейно

Таким образом, эффективные алгоритмы могут быть основаны на нелинейных малопараметрических аппроксимациях матриц Однако далеко не всегда очевидно, как получить эффективное малопараметрическое представление матрицы Более того, чтобы быстро работать с такими структурами, мы должны уметь выполнять матричные операции (сложение, умножение, обращение) именно в терминах малопараметрического представления В общем случае возможность сохранения структуры при операциях зависит от выбранного типа структуры Например матрица, обратная к теплицевой матрице, уже не будет теплицевой В то же время теплицевы матрицы можно вложить в более широкий класс матриц малого ранга смещения, который уже замкнут относительно операции обращения К сожалению, даже этот класс не замкнут относительно операции умножения Поэтому выполнение матричных операций с сохранением малопараметического формата может быть только приближенным Теплицевы матрицы соответствуют одномерным интегральным уравнениям, где использование сеток большой размерности не является необходимым На практике значительно более интересным представляется решение многомерных уравнений Для ядер, инвариантных относительно сдвига и дискретизации на равномерной сетке, получаются многоуровневые теплицевы матрицы Такие матрицы тоже можно умножать на вектор за квазилинейное время, однако до сих пор универсальных прямых методов решения таких систем за то же время неизвестно Существующие формулы (формулы Гохберга-Хайнига) содержат не 0(1^) параметров, а 0(1Ч3/2), и, видимо, удобных формул с меньшим числом параметров не существует Что же делать7 Ответ прост Вместо точных формул мы предлагаем использовать некоторые приближённые формулы Из каких соображений можно исходить при получении приближенных формул7 По существу, изучению этого вопроса (или, точнее, методов поиска ответа на данный вопрос) и посвящена данная диссертация

Первая глава диссертации направлена на построение циркулянтных пре-добуславливателей для общих и теплицевых матриц Теплицевы и цирку-лянтные матрицы — матрицы линейной структуры, и в многочисленных предыдущих работах использовались лишь методы на основе наилучших (в некоторой норме) линейных приближений заданной теплицевой матрицы циркулянтами Мы формулируем новую задачу — задачу нелинейной аппроксимации заданной матрицы суммой циркулянта и матрицы малого ранга Раздел 1 1 содержит краткое описание существующих циркулянтных предобуславливателей, состояния дел на данный момент и мотивацию новой задачи — о поиске С + К аппроксимации В разделе 1 2 даются различные формулировки задачи С + И аппроксимации и показывается, как эта задача связана с восстановлением неизвестных элементов в малоран-

говой матрице (матрица с «черными точками») В разделе 1 3 формулируется алгоритм черных точек для решения задачи D + R аппроксимации, к которой сводится задача С + R аппроксимации Этот алгоритм является конечным Доказана теорема о том, что алгоритм восстанавливает подавляющее большинство «пропусков» за конечное число итераций, на практике порядка 10-20 В разделе 1 4 формулируется практическая адаптивная версия метода черных точек, позволяющая строить С + R и D + R аппроксимации без какой-либо дополнительной информации — на вход надо лишь подать исходную матрицу и нужный параметр точности аппроксимации г Для матриц общего вида, описываемых п2 параметрами, получается алгоритм сложности 0(п2) Для теплицевых матриц, определимых 2п — 1 параметром, в разделе 1 5 получен алгоритм сложности ü(nlogn) Основная задача, которую потребовалось решить — дать удобное, легко и быстро вычисляемое описание для Фурье-образа теплицевой матрицы

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

Теорема 1 Пусть теплицева матрица Т порождена рациональным тригонометрическим символом

т=р(г}+Ш' z==ett'

где Р, Q, L — многочлены, L не имеет корней на единичной окружности, степень Q меньше степени L и они не имеют общих корней Тогда

Т = С + R,

где С-циркулянтная матрица, и при этом rank R ^ deg Р + deg L + 1 Результаты раздела объединяет следующая

Теорема 2 Пусть теплицева матрица Т порождена кусочно-аналитическим символом вида

I m

f=9 + IX Aka(z - ik)a log(z - ck), г = elt, |Ck| = 1,

a=0 k=0

где функция g является аналитической в кольце, содержащем \z\ = 1 Тогда для любого е существуют циркулянтная матрица С и матрица R такие, что

|(T-C-R)4K|T4|e,

причем

rank R < log е 1 [c0 + ci log e 1 + c2logn] + c3,

(1)

а со.сьсг.сз не зависят от n и e

Оказывается, что класс функций, к которым применима теорема 2, включает в себя все примеры в литературе по суперлинейным предобуславли-вателям

В разделе 1 7 приведены численные эксперименты по построению C+R аппроксимаций для различных теплицевых матриц В разделе 1 8 идея метода черных точек получает свое естественное продолжение приведен вариант метода, позволяющий восстанавливать неизвестные элементы в малоранговой матрице с произвольным расположением этих самых неизвестных элементов Однако, в отличие от диагонального шаблона, надо внимательно следить за тем, какие элементы удалось восстановить, а какие нет. В разделе 1 9 сделано самое общее возможное обобщение метода черных точек на случай, когда положение неизвестных элементов неизвестно Для этого предложено максимизировать разреженность матрицы А — R с помощью минимизации специального функционала

Вторая глава посвящена построению специальных преобразований (вейв-лет-преобразований) для сжатия матриц, построенных по неравномерным сеткам Построение происходит на основе лифтинговой схемы В разделе 2 1 описывается история вопроса и мотивируется необходимость построения таких новых преобразований В разделе 2 2 даются основные понятия и определения, необходимые для дальнейшего изложения В разделе 2 3 вводится самый важный в главе объект — вейвлет-пространство и описывается так называемая лифтинговая схема построения вейвлет-преобразований с требуемыми свойствами В разделе 2 4 формулируются основное требование на вейвлет-преобразование (наличие заданного количества нулевых моментов) и выписывается система линейных уравнений специального вида на коэффициенты, определяющие искомое преобразование В разделе 2 5 формулируется основной результат главы Показано, что задача сводится к нахождению некоторых многочленов Р, (х), Jmin ^ j < Vax таких, ЧТО

)ш1П ^ Т ^ ]тах>

где х, — некоторая заданная неравномерная сетка на отрезке После этого доказывается следующая теорема о виде этих полиномов

(2)

Теорема 3 Многочлен Р, (х) такой что

\0))<т<)тах + 1) ^ ;

удовлетворяет (2) при к = О Многочлен Р, (х) такой, что

= (4)

[0,)<г^та + к+1, ^

Ч(х) = (х, -х(,+к+1)) (х-хг), 1=)+1

удовлетворяет (2) при к ^ 1

Раздел 2 6 посвящен нахождению масштабирующих коэффициентов — показано, что их можно находить с помощью уже описанного алгоритма по аналогичным формулам В разделе 2 7 описан конкретный пошаговый способ реализации вейвлет-преобразования, требующий О(п) операций Также описаны алгоритмы вычисления обратного и обратного транспонированного преобразования — они активно используются в численных расчетах для восстановления исходных данных по преобразованным В разделе 2 8 приведены численные эксперименты, сравнивающие новые преобразования с преобразованиями Добеши Показано, что выигрыш по степени сжатия составляет в различных примерах от 30% до 50% процентов

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

Пусть дана матрица А, тогда метод Ньютона для ее обращения записывается в виде

Хк = 2Хк_1 - Хк_! АХк_1, Хк -» А"1, (5)

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

Поэтому в разделе 3 4 описан метод Ньютона с аппроксимациями, позволяющий строить приближенные обратные к большим структурированным матрицам

2Ч = 2Х]с_1 - Хк_, АХк_!, Хк = 1?(гк), (6)

где К — оператор обрезания (или аппроксимации) Справедлива следующая теорема

Теорема 4 Предположим, что

1?(А~1) = А-1 (7)

Тогда, для всех достаточно близких к А-1 начальных приближений Хо = И(Хо) метод (6) порождает последовательность матриц Хк, сходящуюся к А-1 квадратично

ЦА-1-Хк||<(1+М)||А|| НА-'-Х^Н2, к=1,2, ... (8)

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

Порядок матрицы 16129 65025 261121 1046529

Тензорный ранг 20 22 25 20

Точность 9 7 10"8 8 4 Ю-8 9 8 10-« 81 10"6

Матрица-на-вектор 0 3 sec 1 6 sec 7 7 sec 15 6 sec

Число итераций 28 30 33 38

Построение нредобуславливателя 4 0 sec 16 4 sec 1 1 min 4 4 min

Время решения 11 2 sec 59 4 sec 5 7 mm 14 5 min

Относительная ошибка 5 8 10-' 1 1 10"6 9 9 10"' 2 8 10"b

Таблица 1 Результаты для неравномерной сетки

Четвёртая глава посвящена обращению двухуровневых теплицевых матриц В рамках развиваемого подхода построен метод Ньютона с аппроксимациями для обращения двухуровневых теплицевых матриц с использованием введенного TDS-формата (Tensor-displacement-structure) Сам новый формат вводится в разделе 4 2В разделе 4 3 описываются основные арифметические операции над матрицами в TDS формате — сложение, умножение, и показывается, что их можно выполнить за C(v/nlogan) операций Важнейший элемент одного шага метода Ньютона — оператор обрезания — описан в том же разделе Показано, что задача сводится к вычислению фробениусова скалярного произведения двух TDS-матриц, и

это вычисление может быть проведено очень быстро В разделе 4 5 описывается способ выбора начального приближения В разделе 4 6 приведены численные эксперименты для двух модельных задач Для матрицы из уравнения Прандтля результаты приведены в таблице 2

Порядок матрицы 642 1282 2562 5122

Время счета 270 сек 433 сек 817 сек 1710 сек

Тензорный ранг А-1 13 13 12 11

Средний ранг смещения А-1 85 93 9 5 97

Таблица 2 Численные результаты для модельной задачи

И, наконец, в разделе 4 7 впервые получены теоретические результаты о структуре обратных матриц к матрицам малого тензорного ранга специального вида Построен класс матриц, замкнутый относительно обращения Самым простым примером такой матрицы является матрица вида

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

Основные результаты работы

1 Решена задача построения оптимальных циркулянтных предобу-славливателей на основе эффективных алгоритмов построения С+И иИ+К аппроксимаций Предложен и теоретически обоснован метод черных точек для решения задачи С + И и Б + И аппроксимации и для восстановления пропусков в больших малоранговых матрицах Для всех практически важных случаев теплицевых матриц доказаны теоремы о существовании С + И аппроксимации

2 Построены явные формулы для построения вейвлет-преобразований на неравномерных сетках Показано, что адаптированные к заданной сетке вейвлет-преобразования дают существенный выигрыш по сравнению с классическими преобразованиями Добеши, от 30% до 50%

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

4 Построен алгоритм супер-быстрого обращения двухуровневых теп-лицевых матриц, основанный на разработанном методе Ньютона с аппроксимациями Предложена приближенная структура (TDS-фор-мат) для обратной матрицы к дважды теплицевой матрице — тензорное разложение малого тензорного ранга, в котором каждый тензорный фактор имеет малый ранг смещения На модельных примерах показано, что сложность алгоритма для обращения двухуровневых теплицевых матриц порядка п составляет 0(-^/nlogan), те алгоритм имеет сублинейную сложность по порядку матрицы п Впервые получены результаты о структуре матриц, обратным к матрицам малого тензорного ранга специального вида

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

1 Оселедец И В , Тыртышников Е.Е , Приближенное обращение матриц при численном решении гиперсингулярного интегрального уравнения ЖВМ и МФ , 2005, 45 2, 315-326

2 Оселедец И В , Применение разделенных разностей и В -сплайнов для построени быстрых дискретных преобразований вейвлетовского типа на неравномерных сетках, Мат заметки, 2005, 75 5, 743-752

3 Замарашкин Н Л , Оселедец И В , Тыртышников Е Е , О приближении теплицевых матриц суммой циркулянта и матрицы малого ранга, ДАН, 2006, 73,100-101

4 Ford J М , Oseledets I V , Tyrtyshnikov E E , Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids, Rus J Numer Anal and Math Modelling, 2004, 19 2, 185-204

5 Оселедец И В , Оценки снизу для сепарабельных аппроксимаций ядра Гильберта, Матем сб, 2007, 198 3, 137-144

6. Оселедец И В , Савостьянов Д В , Ставцев С Л , Применение нелинейных методов аппроксимации для быстрого решения задачи о распространении звука в мелком море Методы и технологии решения больших задач, ИВМ РАН, 2004, 171-192

изд лиц №03991 от 12 02 2001 Компьютерный набор Подписано в печать 10 10 2007 Уел печ л 0 8 Тираж 100 экз

Институт вычислительной математики РАН 119333, Москва, ул Губкина, 8

Введение

1.1 Нелинейные аппроксимации матриц: зачем и как

2 Основные результаты работы.

1.3 Содержание работы по

главам

Глава 1. Метод чёрных точек и наилучшие циркулянтные предобуславливатели

1.1 Введение.

1.2 Задачи С+Я и Б+К аппроксимации.

1.3 Чёрные точки, малые ранги и скелетоны.

1.4 Адаптивная версия метода чёрных точек.

1.5 Тёплицев случай.

1.5.1 Быстрое вычисление образа Фурье для тёплицевой матрицы.

1.6 Существование С+Я аппроксимации для некоторых классов тёплицевых матриц.

1.7 Численные эксперименты.

1.8 Метод чёрных точек для произвольного шаблона

1.9 Неизвестный шаблон.

1.10 Выводы.

Глава 2. Нестандартные вейвлет-преобразования

2.1 Введение.

2.2 Основные понятия и определения.

2.3 Вейвлет-пространство. Масштабирующие и лифтинговые коэффициенты.

2.4 Основная система.

2.5 Решение основной системы.

2.6 Нахождение масштабирующих коэффициентов.

2.7 Алгоритм вычисления вейвлет-преобразования.

2.8 Численные эксперименты.

2.8.1 Пример 1.

2.8.2 Пример 2.

2.9 Выводы.

Глава 3. Тензорные аппроксимации матриц со структурированными факторами

3.1 Введение.

3.2 Масштабированные циркулянтные предобуславливатели

3.3 Приближённое обращение структурированных матриц

3.4 Методы построения приближённой обратной матрицы

3.4.1 Метод Ньютона с аппроксимациями.

3.4.2 Модифицированный метод Ньютона.

3.5 Численные результаты.

3.5.1 Масштабированный циркулянтный преобуслав-ливатель.

3.5.2 Предобуславливатели на основе метода Ньютона

3.6 Выводы.

Глава 4. Супер-быстрое обращение двухуровневым тёплицевых матриц

4.1 Введение.

4.2 TDS формат.

4.3 Арифметика TDS формата.

4.3.1 Основные арифметические операции.

4.4 Основные арифметические операции в тензорном формате

4.4.1 TDS-рекомпрессия

4.4.2 Оператор обрезания

4.5 Метод Ньютона и выбор начального приближения

4.6 Численные результаты.

4.7 Структура обратных к двухуровневым матрицам специального вида.

4.7.1 Так почему же 5?.

4.7.2 Обобщение на случай большего числа слагаемых

4.8 Выводы.

1. Нелинейные аппроксимации матриц: зачем и как

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

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

Плотные матрицы описываются параметрами. Если мы хотим ускорить работу с ними, то необходимо построить «сжатое» представление матрицы с помощью меньшего числа параметров. Матрицы, описываемые малым числом параметров, будем называть структурированными.

Часто структура матрицы видна сразу или следует из физических свойств задачи. Например, в задачах с оператором, инвариантным относительно сдвига, получающиеся матрицы имеют тёплицеву (или блочно-тёплицеву в многомерных задачах) структуру, т.е. элемент матрицы зависит лишь от разности индексов: а^ = Ь^. Для тёплицевых матриц существуют быстрые алгоритмы, основанные на БПФ. Тёплицевы матрицы — классический пример матриц с линейной структурой. Можно привести другие примеры: ганкелевы матрицы (а^ = ), ленточные матрицы, разреженные матрицы.

Ещё один важнейший класс матриц — матрицы малого ранга, т.е. матрицы вида

А = ИУТ,

II € КПХТ,У е Мтхт, где ранг г < т,п. Это — пример матрицы с нелинейной структурой: её элементы зависят от параметров (элементов матриц II и V) нелинейно.

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

Тёплицевы матрицы соответствуют одномерным интегральным уравнениям, где использование сеток большой размерности не является необходимым. На практике значительно более интересным представляется решение многомерных уравнений. Для ядер, инвариантных относительно сдвига и дискретизации на равномерной сетке, получаются многоуровневые тёплицевы матрицы. Такие матрицы тоже можно умножать на вектор за квазилинейное время, однако до сих пор универсальных прямых методов решения таких систем за то же время неизвестно. Существующие формулы (формулы Гохберга-Хайнига) содержат не 0(14) параметров, а С(Ы3//2), и, видимо, удобных формул с меньшим числом параметров не существует. Что же делать? Ответ прост. Вместо точных формул мы предлагаем использовать некоторые приближённые формулы. Из каких соображений можно исходить при получении приближённых формул? По существу, изучению этого вопроса (или, точнее, методов поиска ответа на данный вопрос) и посвящена данная диссертация.

4.8. Выводы

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

Заключение

В заключение диссертации сформулируем её основные результаты.

1. Решена задача построения оптимальных циркулянтных предобу-славливателей на основе эффективных алгоритмов построения С + И и О + И аппроксимаций. Предложен и теоретически обоснован метод чёрных точек для решения задачи С + И и Э + И аппроксимации. Для всех практически важных случаев тёплице-вых матриц доказаны теоремы о существовании С + К аппроксимации.

2. Построены явные формулы для построения вейвлет-преобраз-ований на неравномерных сетках. Показано, что адаптированные к заданной сетке вейвлет-преобразования дают существенный выигрыш по сравнению с классическими преобразованиями Добеши, от 30% до 50%.

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

4. Построен алгоритм супер-быстрого обращения двухуровневых тёплицевых матриц основанный на разработанном методе Ньютона с аппроксимациями. Для тёплицевых матриц подходящей структурой оказались матрицы малого тензорного ранга, причём каждый фактор имеет малый ранг смещения. На модельных примерах показано, что сложность алгоритма для обращения двухуровневых тёплицевых матриц составляет 0(\/пЛс^ап), т.е. алгоритм имеет сублинейную сложность. Впервые получены результаты о структуре матриц, обратным к матрицам малого тензорного ранга специального вида, и показано, что обратные к матрицам, получающающимся при дискретизации двумерного интегрального уравнения, могут быть аппроксимированы матрицами малого тензорного ранга со структурированными факторами. Число параметров в таком структурированном представлении ведёт себя как 0[л/п) — меньше, чем линейный размер матрицы.

1. М. Bebendorf, Approximation of boundary element matrices, Numer. Math., 2000, 86, 565-589.

2. M. Bebendorf and S. Rjasanow, Adaptive low-rank approximation of collocation matrices, Computing, 2003, 70, 1-24.

3. M. Bebendorf, S. Rjasanow and Б. Б. Tyrtyshnikov, Approximation using diagonal-plus-skeleton matrices, Math. asp. of bound, elem. meth. (Palaiseau, 1998), Chapman Hall/CRC, Boca Raton, FL, 2000, 45-52.

4. R. Chan, Circulant preconditioners for Hermitian Toeplitz systems, Linear Algebra Appl., 1989, 10, 542-550.

5. T. F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 1988, 9, 766-771.

6. R. H. Chan, D. Potts, G. Steidl, Preconditioners for Nondefinite Hermitian Toeplitz Systems, SIAM Matrix Anal. Appl, 2001, 22:3, 647-665.

7. R. H. Chan, M. K. Ng and A. M. Yip, A Survey of Preconditioners for 111-Conditioned Toeplitz Systems, Structured Matrices in Mathematics, Computer Science, and Engineering II, Contemporary Mathematics, 2001, 281, 175-191.

8. I. Daubechies. Orthonormal bases of compactly supported wavelets. Communications of Pure and Applied Mathematics, October 1988, 41:7, 909-996.

9. B. W. Dickinson, Solution of linear equations with rational Toeplitz matrices, Math. Comput., 1980, 34:149, 227-233.

10. T. A. Driscoll and B. Fornberg, A Padie-based algorithm for overcoming the Gibbs phenomenon, Numerical Algorithms, 2001, 26, 77-92.

11. J. M. Ford, E. E. Tyrtyshnikov, Combining Kronecker product approximation with discrete wavelet transforms to solve dense, function-related systems, SI AM J. Sci. Comp., 2003, 25:3, 961-981.

12. I. Gohberg, G. Heinig, Inversion of finite-section Toeplitz matrices consisting of elements of a non-commutative algebra, Rev. Roum. Math. Pures et Appl, 1974, 19:5, 623-663.

13. S. A. Goreinov, E. E. Tyrtyshnikov, The maximal-volume concept in approximation by low-rank matrices, Contemporary Mathematics, 2001, 208, 47-51.

14. S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudo-skeleton approximations, Linear Algebra Appl, 1997, 261, 1-21.

15. W. Hackbusch, A sparse matrix arithmetic based on 7i -matrices. I. Introduction to H-matrices, Computing, 1999, 62:89-108.

16. W. Hackbusch, B. N. Khoromskii, A sparse H-matrix arithmetic. II. Application to multi-dimensional problems, Computing, 2000, 64, 21-47.

17. W. Hackbusch, B. N. Khoromskii, E. E. Tyrtyshnikov, Hierarchical Kronecker tensor-product approximations, Max-Panck-Institut fur Mathematik in den Naturwissenschaften, Leipzig, Preprint No. 35, 2003.

18. W. Hackbusch, Z. P. Nowak, On the fast matrix multiplication in the boundary elements method by panel clustering, Numer. Math., 1989, 54:4, 463-491.

19. G. Heinig, K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Berlin, Academie-Verlag, 1984.

20. H. Hotelling, Analysis of a complex of statistical variables into principal components, J. Educ. Psych., 1933, 24, P I: 417-441, P II: 498-520.

21. T. Kailath, S. Kung, M. Morf, Displacement ranks of matrcies and linear equations, J. Math. Anal.and Appl, 1979, 68, 395-407.

22. J. Kamm, J. G. Nagy, Optimal Kronecker Product Approximations of Block Toeplitz Matrices, SIAM J. Matrix Anal Appl., 2000, 22:1, 155-172.

23. T.-K. Ku, C.-C. J. Kuo, Spectral properties of preconditioned rational Toeplitz matrices: the nonsymmetric case, SIAM J. Matrix Anal. Appl., 1993, 14:2, 512-544.

24. D. Noutsos, S. Serra Capizzano, P. Vassalos, A preconditioning proposal for ill-conditioned Hermitian two-level Toeplitz systems, Numer. Linear Algebra Appl, 2005, 12, 231-239.

25. V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Physics, 1985, 60, 187-207.

26. Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, An International Thomson Publishing Company, Boston, 1996.

27. L. Schumaker, Spline functions : basic theory, Wiley, New York, 1981.

28. G. Schulz, Iterative Berechnung der reziproken Matrix, Z. angew. Math, und Mech., 1933, 13:1, 57-59.

29. G. Strang, A proposal for Toeplitz matrix calculations, Studies in Applied Mathematics, 1989, 84, 171-176

30. V.V.Strela and E.E.Tyrtyshnikov, Which circulant preconditioner is better? Math. Comput., 1996, 65:213, 137-150.

31. W. Sweldens, The lifting scheme: A custom design construction of biorthogonal wavelets, Appl Comput. Harmon. Anal, 1996, 3, 186200.

32. W. F. Trench, An algorithm for the inversion of finite Toeplitz matrices, SIAM J.Appl Math., 1964, 12, 515-521.

33. E. E. Tyrtyshnikov, Kronecker-product approximations for some function-related matrices, Linear Algebra Appl, 2004, 379, 423-437.

34. Е. Е. Tyrtyshnikov, Optimal and superoptimal circulant preconditioners, SI AM J. Matrix Anal. Appl, 1992, 13:2, 459-473.

35. E. E. Tyrtyshnikov, Incomplete cross approximation in the mosaic-skeleton method, Computing, 2000, 64:4, 367-380.

36. E. E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 1996, 232, 1-43.

37. E. E. Tyrtyshnikov, Mosaic-skeleton approximations. Calcolo, 1996, 33:(l-2), 47-57.

38. E. E. Tyrtyshnikov, R. Chan, Spectral Equivalence and Proper Clusters for Boundary Element Method Matrices, Int. J. Numer. Meth. Engnr., 2000, 49, 1211-1224.

39. E. E. Tyrtyshnikov, N. L. Zamarashkin, and A. Yu. Yeremin, Clusters, preconditioners, convergence, Linear Algebra Appl., 1997, 263, 2548.

40. C. F. Van Loan , N. P. Pitsianis, Approximation with Kronecker products, NATO Adv. Sci. Ser. E Appl. Sci., 1993, 232, 293-314.

41. N. Yarvin, V. Rokhlin, Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput, 1999 20:2, 699-718.

42. A.А. Акопян, А.А. Саакян. Многомерные сплайны и полиномиальная интреполяция. Успехи математических наук, 1993, 48:5.

43. С. М. Белоцерковский, И. К. Лифанов, Численные методы в сингулярных интегральных уравнениях, М., Наука, 1985.

44. B.А. Василенко Сплайн-функции: теория, алгоритмы, программы, Новосибирск: Наука, 1983. 216 с.

45. B. В. Воеводин, Е. Е.Тыртышников, Вычислительные процессы с теплицевыми матрицами, М., Наука, 1987.

46. C. А. Горейнов, Н. Л. Замарашкин, Е. Е. Тыртышников, Псевдоскелетные аппроксимации матриц, ДАН, 1995, 343:2, 151-152, 1995.

47. И. Ц. Гохберг, А. А. Семенцул, Об обращении конечных тёплице-вых матриц и их непрерывных аналогов, Матем. исслед., 1972, 7:2, 201-224.

48. И. Добеши. Десять лекций по вейвлетам, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001

49. С. А. Довгий, И. К. Лифанов, Методы решения интегральных уравнений, Наукова Думка, Киев, 2002.

50. И. К. Лифанов, Б. Е. Тыртышников, Теплицевы матрицы и сингулярные интегральные уравнения, Вычислительные процессы и системы, Вып. 7, 94-278. М., Наука, 1990.

51. И. К. Лифанов, Л. Н. Полтавский, Обобщенные операторы Фурье и их применение к обоснованию некоторых численных методов в аэродинамике, Матем. сб., 1992, 5, 79-114.

52. Е. Е. Тыртышников, Тензорные аппроксимации матриц, порожденных асимптотически гладкими функциями, Матем. сб., 2003, 194:6, 147-160.

53. Е. Е. Тыртышников, Методы быстрого умножения и решение уравнений, Матричные методы и вычисления, ИВМ РАН, Москва, 1999, 4-41.

54. Е. Е. Тыртышников, Тензорные аппроксимации матриц, порожденных асимптотически гладкими функциями, Матем. сб., 2003, 194:6, 147-160

55. Д. К. Фаддеев, В. Н. Фаддеева, Вычислительные методы линейной алгебры, М.-Л., Физматгиз, 1963.

56. К. Чуй. Введение в вейвлеты, Москва, «Мир», 2001

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

58. V. Olshevsky, I. Oseledets, Е. Tyrtyshnikov, Tensor properties of multilevel Toeplitz and related matrices, Linear Algebra Appl., 2006, 412, 1-21.

59. Oseledets I.V., Tyrtyshnikov E.E., A unifying approach to the construction of circulant preconditioners, Linear Algebra Appt., 2007, 418, 435-449.

60. Оселедец И.В., Тыртышников Е.Е., Приближённое обращение матриц при численном решении гиперсингулярного интегрального уравнения ЖВМ и МФ , 2005, 45:2, 315-326.

61. Оселедец И.В., Применение разделённых разностей и В-сплайнов для построени быстрых дискретных преобразований вейвлетов-ского типа на неравномерных сетках, Мат. заметки, 2005, 75:5, 743-752

62. Замарашкин H.A., Оселедец И.В., Тыртышников Е.Е., О приближении тёплицевых матриц суммой циркулянта и матрицы малого ранга, ДАН, 2006, 73, 100-101.

63. Ford J. М., Oseledets I. V., Tyrtyshnikov E. E., Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids, Rus. J. Numer. Anal, and Math. Modelling, 2004, 19:2, 185-204.

64. Оселедец И.В., Оценки снизу для сепарабельных аппроксимаций ядра Гильберта, Матем. сб., 2007, 198:3, 137-144.

65. Оселедец И.В., Савостьянов Д.В., Ставцев С.Л., Применение нелинейных методов аппроксимации для быстрого решения задачи о распространении звука в мелком море. Методы и технологии решения больших задач, ИВМ РАН, 2004, 171-192.