Обзор свободных программ для численных расчётов

Хочу предложить небольшой обзор свободного программного обеспечения для численных расчётов. Прежде всего для решения систем уравнений в частных производных (УрЧП). Решать их нужно во многих инженерных и начных областях (в гидродинамике, теории упругости, теплопроводности, электромагнетизме и других). К счастью, в этой области написано много качественных свободных программ. И учитывая, что GNU/Linux — сегодня главная платформа для численных расчётов, это неудивительно. К сожалению, не все, кому приходится впервые сталкиваться с численными расчётами знают об этих программах. Чаще всего на слуху пара названий коммерческих продуктов с закрытым исходным кодом, ограниченными возможностями расширения и астрономической ценой. Этим мини-обзором я хочу исправить такую ситуацию и рассказать о свободных программах. Я надеюсь, этот обзор будет полезен тем, кто начинает заниматься численными расчётами и ищет подходящее программное обеспечение.

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

Линейная алгебра

Работа с системами линейных уравнений означает, что программа должна эффективно работать с матрицами и векторами. Общепринятым «стандартом» для операций с ними являются библиотеки BLAS (основные операции) и LAPACK. Оптимизация этих библиотек оказывает большое влияние на эффективность работы программ.

• BLAS, есть несколько программных реализаций, свободные: BLAS c netlib, автоматически оптимизированный ATLAS; несвободные: MKL (Intel), GotoBLAS и другие
• LAPACK

Отдельного упоминания заслуживает FLAME, проект по созданию современной библиотеки для линейной алгебры. В целом, он обратно совместим с BLAS и LAPACK, большое внимание уделяется понятной записи и верифицируемость алгоритмов, есть несколько разных API (C, Matlab/Octave), поддерживаются вычисления на GPU.
Существуют и распараллеленные библиотеки:

• PLAPACK
• ScaLAPACK
• Elemental (основан на FLAME)

Решение систем линейных уравнений

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

• Прямые методы
  • UMFPACK
  • SuperLU
  • TAUCS (библиотека включает и итерационные алгоритмы)
• Итерационные методы
  • Многие методы могут быть легко реализованы самостоятельно, см. книжку Templates for the solution of linear systems: building blocks for iterative methods
  • PETSc (возможность распараллеливания по MPI)
  • LASPACK (включает многосеточные методы, но годится только для последовательных машин)
  • TAUCS (библиотека включает и прямые алгоритмы)
  • Aztec (библиотека для параллельного итерационного решения линейных систем, эффективная, с доступным исходным кодом, но несвободной лицензией)

Работа с (разреженными) матрицами

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

• Fortran
  • UMFPACK
  • SuperLU
  • PETSc
  • SPARSKIT2
• C
  • UMFPACK
  • SuperLU
  • PETSc
  • TAUCS
• C++ (часто предоставляется более удобный и наглядный синтаксис операций)
  • TNT (просто и сердито, один inlcude-файл)
  • FLENS (включает также эффективный, удобный и элегантный интерфейс к BLAS и LAPACK)
  • uBLAS (интерфейс к BLAS из коллекции библиотек Boost)
  • GMM++ (предоставляет единый интерфейс к разным решателям, успешно используется в GetFEM++)
  • Blitz++ (вообще говоря, не поддерживает разреженные матрицы, но это очень эффективная библиотека, если нужны плотные многомерные матричные структуры, но без линейной алгебры)
  • Seldon (не пробовал)
  • SparseLib++ (не пробовал)
  • + всё то же самое, что и в C
• Python
  • PySparse (есть в Debian)
  • petsc2py (интерфейкс к PETSc из Python)

Ознакомьтесь также со сравнением производительности C++-библиотек для работы с разреженными матрицами, если вас интересуют вопросы быстродействия.