Общая информация     Научные направления    Ученый совет    Диссертационный совет    Сотрудники    Семинары

Конференции    Проекты    Отчеты    Публикации    Инновации    Кластер ИВМ    Кафедры    Аспирантура

Матричные методы и технологии решения больших задач (под ред. Е.Е.Тыртышникова), ИВМ РАН, 2005.

ПРЕДИСЛОВИЕ

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

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

Если общее число узлов есть величина порядка 10^6, то общее число ненулевых числовых коэффициентов будет порядка 10^12. Если для хранения одного числа используется 8 байт, то для всего массива коэффициентов потребуется более 7 терабайт. Это не так уж мало. Но более серьезной проблемой является то, что традиционные методы решения систем уравнений имеют время работы, пропорциональное кубу числа узлов. Поэтому если допустить, что для 10^3 узлов требуется время порядка 0.1 секунды, то для 10^6 потребуется уже около 1200 суток, то есть более 3 лет.

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

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

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

Особенно следует отметить успехи в области построения тензорных аппроксимаций на основе неполной информации об исходных данных. Получен быстрый метод одновременного приближённого приведения семейства матриц к треугольному виду. На основе этого метода разработан алгоритм построения трилинейной аппроксимации трёхмерных массивов, позволяющий находить разложения массива с размерами 128x128 x128 и тензорным рангом 128 за несколько минут. Разработаны эффективные методы трилинейной аппроксимации для трёхмерных массивов (тензоров) с рангом, превышающим размеры тензора. Построен эффективный алгоритм неполной крестовой аппроксимации для многомерных массивов, позволяющий находить разложения Таккера для кубического массива размера n в кубе с почти линейной асимптотикой сложности по n. Созданный на основе разработанных методов программный комплекс позволяет строить трилинейное разложение в случае n=65536 за время порядка часа на обычной персональной ЭВМ, и тем самым снижать затраты на его хранение с 2 петабайт (2^50 байт) до нескольких десятков мегабайт.

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

Е.Е. Тыртышников