Содержание к диссертации
Введение
Глава 1. Мозаично-скелетониый метод 20
1.1 Описание и развитие мозаично-скелетонного метода . 20
1.1.1 Описание метода 20
1.1.2 Методы дожимания (переаппроксимации) 24
1.1.3 Численные эксперименты 25
1.2 Параллельная версия метода 26
1.2.1 Особенности кластерных станций 27
1.2.2 Модель параллелизации и распределение нагрузки. 28
1.3 Выводы 29
Глава 2. Метод трехмерной крестовой аппроксимации 31
2.1 Введение 31
2.2 Теорема существования 35
2.3 Трехмерный крестовый метод 38
2.3.1 Как нельзя построить этот алгоритм 38
2.3.2 Как можно построить этот алгоритм 40
2.3.3 Как добиться почти линейной сложности 40
2.3.4 Как сделать алгоритм эффективным 45
2.3.5 Сложность полученного метода 51
2.4 Важные детали 54
2.4.1 Как найти подматрицу максимального объема 54
2.4.2 Как найти наибольший элемент в срезке 57
2.4.3 Как добавить векторы в ортогональный набор 60
2.4.4 Как проверять точность аппроксимации 63
2.4.5 Какова точность «нулевого приближения» . 64
2.5 Модельные численные эксперименты 66
2.6 Асимптотика предложенного метода 67
2.6.1 Теоретические оценки 67
2.6.2 Практические значения ранга 72
2.6.3 Время работы алгоритма 73
2.7 Выводы 83
Глава 3. Приложения к численному решению уравнений 84
3.1 Применение мозаично-скелетонного метода к задаче Дирихле для уравнения Гельмгольца 84
3.1.1 Некоторые факты из теории потенциала 84
3.1.2 Интегральное уравнение и дискретизация 86
3.1.3 Численные эксперименты 89
3.2 Применение мозаично-скелетонного метода к задаче гидроакустики 92
3.2.1 Постановка задачи 92
3.2.2 Метод замкнутых дискретных вихревых рамок 95
3.2.3 Вычисление элементов матриц 96
3.2.4 Численные эксперименты 97
3.3 Применение тензорных аппроксимаций к решению простейшего интегрального уравнения 98
3.3.1 Постановка задачи 98
3.3.2 Дискретизация задачи 98
3.3.3 Сжатие матрицы 99
3.3.4 Структурированные векторы 100
3.3.5 Предобусловливание тензорных матриц 101
3.3.6 Численные результаты 105
3.4 Выводы 106
Глава 4. Специфика матриц в одной задаче электродинамики 108
4.1 Постановка задачи 108
4.1.1 Физическая постановка 108
4.1.2 Интегральное уравнение 110
4.2 Метод дискретизации 112
4.3 Специфика полученной матрицы 113
4.4 Параллельный алгоритм 115
4.5 Численные эксперименты 119
4.6 Пример решения обратной задачи 128
4.6.1 Приближение Борна 128
4.6.2 Горизонтальное зондирование 130
4.6.3 Двумерное зондирование 131
4.7 Применение трилинейной крестовой аппроксимации для сжатия данных 131
4.8 Выводы 134
Заключение 135
Литература 137
- Описание и развитие мозаично-скелетонного метода
- Теорема существования
- Некоторые факты из теории потенциала
- Интегральное уравнение
Введение к работе
Актуальность работы
Диссертация посвящена построению быстрых методов приближенного умножения на плотные неструктурированные матрицы, возникающие при численном решении интегральных уравнений. Сложность заключается в том, что возникающие плотные матрицы обычно слишком большие, и их нельзя разместить в оперативной памяти компьютера или на жестком диске, а часто и вычислить за разумное время. Снижение размерности возникающих систем за счет выбора хорошей адаптивной сетки и аккуратного способа построения дискретизации является теоретически и практически сложной проблемой, решение которой требует глубокого изучения свойств исходной задачи. Зачастую в инженерных расчетах детальный анализ задачи не может быть произведен (в силу нехватки времени или информации о свойствах задачи) и дискретизация происходит на несложной, но чрезмерно мелкой сетке с использованием простых базисных функций. Для сохранения хорошей точности моделирования приходится рассматривать и решать линейные системы больших и очень больших размеров. При этом в них содержится много избыточной информации, которую можно без большого ущерба для точности отбросить, значительно снизив число параметров, описывающих систему. Автоматическое обнаружение специфики исходных задач и получение малопараметрической аппроксимации заданных линейных систем — интересная и практически важная задача.
В работах Е. Е. Тыртышникова было показано, что с алгебраической точки зрения многие быстрые подходы к решению интегральных уравнений (мультипольные разложения, кластеризация граничных элементов, интерполяция на регулярную сетку, локальные волны) явно или неявно базируются на одном и том же наблюдении: для весьма широкого класса ядер матрицы, возникающие при дискретизации, могут быть разбиты на блоки, большинство из которых близки к матрицам малого ранга. В предложенном им же методе неполной крестовой аппроксимации для каждого блока строится билинейная аппроксимация ац « ац = Y-lc=] ui«vj«) гАе ранг г мал по сравнению с размерами блока. В результате для матрицы Л размера N х N строится аппроксимация Л, такая что ||А — A||f ^ ||A||f, и хранение Л и умножение на нее требует 0{N logaN logb _1) (a > О, b > 0) ячеек памяти и арифметических действий соответственно.
При решении трехмерных объемных интегральных уравнений на тензорных сетках элементы матрицы Л определяются шестью индексами ац = 0-^1.21.3)1)2)3 и М0ГУТ быть аппроксимированы в виде трилинейной
СУММЫ аіиггзітіз ~ й(іі)і)(І2)2)(із)з) = La=1 U(iiji )aV(i2j2)aW(i3J3)a- Матрица
при этом представляется суммой прямых (кронекеровых) произведений
A « A = YJa=] ^« x Va x Wa. Как метод эффективного представления данных трилинейные аппроксимации дают сверхлинейное сжатие, их использование при решении линейных систем приводит к алгоритмам сублинейной сложности, что значительно расширяет возможности применения объемных интегральных уравнений при решении трехмерных задач.
Существующие подходы к построению трилинейного разложения не позволяют оперировать большими объемами данных, характерными для интегральных уравнений. Поэтому развитие быстрого метода вычисления трилинейной аппроксимации — актуальная задача. Кроме интегральных уравнений, трилинейная аппроксимация применяется также при обработке результатов эксперимента, сигналов, статистических данных, больших массивов графической и видео-информации и в других задачах.
Исследования, отраженные в диссертации, поддерживались грантами РФФИ №02-01-00590-а, 04-07-90336-в, 05-01-00721-а и 06-01-08052-офи.
Цели работы
Основная цель работы состоит в развитии эффективного метода неполной крестовой аппроксимации для тензоров (трехмерных массивов). Перед автором были поставлены три задачи:
выяснить, возможно ли построение крестовой аппроксимации для тензоров на основе неполной информации об их элементах;
предложить быстрый алгоритм малопараметрической аппроксимации тензоров по небольшому числу его элементов;
рассмотреть применение этого алгоритма к модельным задачам, используя малопараметрическое представление не только матрицы, но и векторов итерационного процесса.
Методы исследования
Предлагаемые в данной работе алгоритмы малопараметрического описания линейных систем основаны на дискретном аналоге метода разделения переменных. Билинейная аппроксимация — это дискретный аналог расщепления источников и приемников, трилинейная аппроксимация — аналог расщепления по физическим координатам. Отметим, что при построении быстрого алгоритма трехмерной крестовой аппроксимации основное внимание уделено аппроксимации массива [сц^] в виде разложения Таккера
1*1 Г2 Гз
ckjk ~ aljk = ^_ ^_ ^_ gi'j'k'Uii'Vjj'Wkk'
i'=l j'=1 k'=1
с как можно меньшими значениями модовых рангов ті,Г2,тз. При этом задача поиска трилинейного разложения для исходного массива [a-ijiJ сводится к поиску трилинейного разложения для ядра [gi'j'k'L Поскольку размеры ядра много меньше размеров исходного массива, для решения этой задачи можно применить известные алгоритмы поиска трилинейного разложения, такие как супер-обобщенное разложение Шура, метод переменных направлений или метод Гаусса-Ньютона.
Научная новизна работы
Предлагаемый в работе алгоритм трехмерной крестовой аппроксимации (алгоритм 3) является новым и принадлежит автору. Автору не известны другие алгоритмы решения той же задачи, обладающие сравнимой или более низкой асимптотикой сложности. Теоремы, дающие обоснование возможности построения данного метода и корректности его составных частей, являются новыми и принадлежат автору, за исключением теоремы 1, полученной в соавторстве с И. В. Оселедцем и Е. Е. Тыр-тышниковым. Метод билинейной аппроксимации матрицы (алгоритм 1) является одной из возможных модификаций метода неполной крестовой аппроксимации, предложенного Е. Е. Тыртышниковым. Алгоритм поиска подматрицы наибольшего объема, то есть модуля детерминанта (алгоритм 4) предложен С. А. Горейновым. Алгоритмы построения тензорных предобусловливателей (алгоритмы 5 и 6) являются новыми и получены в соавторстве с И. В. Оселедцем. Все прочие результаты являются новыми и принадлежат автору.
Постановка задачи принадлежит Е. Е. Тыртышникову, результаты данной работы следует рассматривать как обобщение для трехмерных тензоров матричных техник, предложенных им же.
Защищаемые положения
На защиту выносятся следующие результаты работы:
Теорема существования трехмерной крестовой аппроксимации, которая строится по небольшому числу столбцов, строк и распорок исходного массива.
Алгоритм трехмерной неполной крестовой аппроксимации. В качестве входного параметра алгоритм использует процедуру вычисления любого элемента массива [a^iJ, однако этот массив не вычисляется и не хранится полностью. Для построения аппроксимации [сц^] в виде разложения Таккера достаточно вычислить порядка 0{пга)
(г = тах(гі,Г2,гз), 1 ^ а ^ 2) элементов массива и совершить порядка 0{пг3) дополнительных действий. Алгоритм следует основным идеям, используемым при построении билинейной аппроксимации в методе неполной крестовой аппроксимации для матриц, и сохраняет главные достоинства этого метода — надежность, высокую эффективность, гибкость в применении к различным типам задач и простоту в практическом использовании.
3. Результаты применения методов полилинейной аппроксимации к модельным и практическим задачам. Тестирование алгоритма трехмерной неполной крестовой аппроксимации на модельном объемном интегральном уравнении и демонстрация сублинейной сложности возникающего метода.
Практическая значимость работы
Методы полилинейной аппроксимации могут быть использованы при численном решении интегральных уравнений, заданных на контурах, поверхностях или в конечном объеме. Они особенно эффективны в случае, когда размерность возникающей линейной системы N слишком велика, чтобы матрицу можно было за разумное время вычислить полностью и разместить в оперативной памяти или на жестком диске. Использование билинейных аппроксимаций в большинстве случаев позволяет снизить сложность вычисления матрицы и умножения на нее до G[N logaN logb -1) с некоторыми a > 0, b > 0. Использование трилинейных аппроксимаций при решении объемных интегральных уравнений на тензорных сетках позволяет снизить сложность этих операций до (9(N2/3 logaN logb _1), то есть до величины асимптотически меньшей числа неизвестных.
Необходимо заметить, что методы би- и трилилинейной аппроксимации позволяют быстро вычислять аппроксимацию матрицы и умно-эюать ее на вектор. Для их успешного применения на практике, как правило, необходимо предобусловливание, то есть приближение обратной матрицы с такими же ограничениями на память и объем вычислений. В работе предлагается способ построения супероптимального тензорного предобусловливателя малого ранга, отвечающего этим требованиям. Для решения трехмерных объемных интегральных уравнений с сублинейной асимптотикой сложности необходимо кроме того использовать в итерационном процессе структурированные векторы. Свойства сходимости возникающих итерационных процессов теоретически пока не изучены, однако в численном эксперименте с модельным уравнением демонстрируется их сходимость и сублинейная сложность.
Хотя в диссертации обсуждается только применение трилинейной аппроксимации для решения интегральных уравнений, трилинейное разложение является вычислительным ядром многих других задач, возникая при обработке данных эксперимента в физике, в задаче о ядерном магнитном резонансе в химии, при обработке сигнала в инженерной практике, слепом разделении сигналов в МШО (multiple-input multiple-output) системах передачи информации, томографии мозга и внутренних органов в медицине, обработке статистического материала в факторном анализе, социологии и экономике, в мультимедийных приложениях для обработки больших массивов графической и видео-информации, в задачах идентификации голоса или образа, в теории сложности при поиске оптимального алгоритма. Во всех этих задачах для эффективного приближенного представления больших плотных массивов данных могут применяться предложенные в диссертации алгоритмы.
Апробация работы
Основные результаты диссертации докладывались на различных конференциях, в т.ч. на международной конференции «Матричные методы и операторные уравнения» (Москва, ИВМ РАН, 2005), на «Ломоносовских чтениях» (Москва, ВМиК МГУ, 2006), на третьей международной конференции «Математические идеи П. Л. Чебышева и их приложение к современным проблемам естествознания» (Обнинск, ИАТЭ, 2006), на 13-ой конференции ILAS (Амстердам, 2006), на «Тихоновских чтениях» (Москва, ВМиК МГУ, 2006); а также на семинаре «Вычислительные и информационные технологии в математике» (научн. рук. ак. В. В. Воеводин, проф. В. И. Лебедев, чл.-корр. Е. Е. Тыртышников, ИВМ РАН).
Публикации
Основные результаты диссертации отражены в публикациях [1-6].
Структура и объем работы
Описание и развитие мозаично-скелетонного метода
Детальное описание мозаично-скелетонного метода дано в работах [37, 51, 38, 11, 39]. Поскольку сам по себе мозаично-скелетонный метод не является центральным объектом изучения в данной работе, мы ограничимся лишь его конспектным изложением. В деталях мы опишем только алгоритм построения скелетонного разложения, послуживший прототипом алгоритма крестового разложения для тензоров. Также в этот раздел включены результаты по развитию метода — техника переаппроксимации и параллельная версия мозаично-скелетонного алгоритма, предложенные в [69].
Описание метода. Будем считать, что решаемая задача сформулирована в виде интегрального уравнения на границе некоторой области, и проведена дискретизация, порождающая линейную систему. Элементы матрицы этой линейной системы и использованная для дискретизации сетка являются входными данными для мозаично-скелетонного алгоритма
Теорема существования
Сложность SVD-разложений составляет C(n4), поэтому применять метод (2.6) непосредственно к массивам Л при н 128 крайне затруднительно. Более того, даже простое вычисление и хранение самого массива А (то есть выполнение С(тт3) операций) может оказаться слишком дорогостоящей задачей при п порядка тысячи.
Для решения этой проблемы предлагается метод, который использует идею алгоритма крестовой аппроксимации [38, 39], и не требует вычисления всех элементов исходной матрицы, а лишь использует процедуру их генерации, вычисляя порядка n log n logY -1 элементов. Положительные числа (3 и у зависят от свойств матрицы А, а определяет требуемую точность аппроксимации. Таким образом, предлагаемый алгоритм обладает той же, почти линейной по п оценкой сложности, то есть строит аппроксимацию ЛТ массива Л за C(nlog 5nlogY-1) операций.
Естественно, для того чтобы по предлагаемому нами алгоритму можно было найти для массива Л трилинейное разложение малого ранга г, точно или с определенной погрепшостью , оно должно существовать. Вопросы существования такого разложения, возникающие требования к массивам Л и теоретические оценки на ранг такого разложения, в зависимости от свойств массива, предложены, например, в работах [40, 67]. В следующем разделе мы покажем, что факторы U,V и VV такого разложения можно составить из некоторых строк, столбцов и распорок массива Л. В дальнейшем при описании алгоритма мы всегда полагаем, что искомая аппроксимация с заданной точностью у рассматриваемого массива существует, и останавливаемся на способе ее поиска. Здесь и далее возникающая в оценках сложности метода величина г будет означать ранг (е-ранг) трилинейного разложения для исходного массива, а об оценках вида 0(nrd) мы будем говорить, как о почти линейных по п.
Некоторые факты из теории потенциала
Некоторые факты из теории потенциала. В качестве первого примера задачи, сводящейся к решению интегрального уравнения, рассмотрим задачу Дирихле для уравнения Лапласа, применив для ее решения методы теории потенциалов.
Пусть в некоторой области О задана функция и, удовлетворяющая внутри области дифференциальному уравнению CU =:0, В О Пусть область О. С 1&т ограничена, ее граница Г ЗО обладает классом гладкости С2. Задача Дирихле для этого уравнения состоит в том, чтобы найти функцию и Є C2(G)f]C{jQ), удовлетворяющую уравнению (3.1) и граничному условию ur = f, (3.2) где f — заданная непрерывная функция.
Существует несколько подходов к решению этой задачи. Дифференциальный подход состоит в том, чтобы построить какую-нибудь сетку внутри О, аппроксимировать на ней дифференциальный оператор и граничное условие, получить алгебраическую дискретизацию задачи Au = f с разреженной матрицей А и решить ее одним из большого числа методов, ориентируясь на полученную картину разреженности. Главные трудности, возникающие при таком подходе, состоят в следующем.
Интегральное уравнение
Физическая постановка. Технологический процесс геологической разведки часто включает в себя метод электромагнитного каротажа, или же зондирования области, с целью определить электромагнитные параметры среды, расположенной в недоступной области за границей шахты. Численная обработка полученных данных измерений основана на решении обратной задачи электромагнитного рассеяния, то есть на определении электромагнитных параметров среды по известной информации об источниках и значениях электромагнитного поля в точках измерения. Решение обратной задачи в существенной степени основано на эффективном алгоритме решения прямой задачи электромагнитного рассеяния, то есть в определении значений электрического и магнитного полей в заданных точках при известной конфигурации источников и заданной геометрии и параметрах среды. Решение прямой задачи может включаться как элемент в алгоритм решения обратной задачи; кроме того, алгоритм решения прямой задачи рассеяния, необходим на этапе отладки алгоритма решения обратной задачи, поскольку позволяет получать данные измерений методом численного, а не физического (более дорогого, менее точного и не всегда возможного) эксперимента.
Прямая задача электромагнитного рассеяния в некотором модельном приближении может быть поставлена так. Рассмотрим распространение электромагнитной волны в полупространстве, ограниченном плоскостью, которая представляет собой идеальный проводник. Будем считать, что зависимость полей от времени гармоническая е іш\ Электрические параметры среды будем считать переменными, но ограничимся моделью локально неоднородной среды, согласно которой среда представляет из себя однородное пространство в котором располагается конечных размеров неоднородность V [65, 64]. Размеры неоднородности предполагаются столь большими, чтобы их увеличение не оказывало существенного влияния на поведение полей в области, где производятся измерения
