Линукс, Vim, LaTeX, полезные скрипты, визуализация данных, численные расчёты, немного ФП

20080325

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

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

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

Основы

Линейная алгебра
Работа с системами линейных уравнений означает, что программа должна эффективно работать с матрицами и векторами. Общепринятым «стандартом» для операций с ними являются библиотеки BLAS (основные операции) и LAPACK. Оптимизация этих библиотек оказывает большое влияние на эффективность работы программ.
  • BLAS, есть несколько программных реализаций, свободные: BLAS c netlib, автоматически оптимизированный ATLAS; несвободные: MKL (Intel), GotoBLAS и другие
  • LAPACK
Отдельного упоминания заслуживает FLAME, проект по созданию современной библиотеки для линейной алгебры. В целом, он обратно совместим с BLAS и LAPACK, большое внимание уделяется понятной записи и верифицируемость алгоритмов, есть несколько разных API (C, Matlab/Octave), поддерживаются вычисления на GPU.
Существуют и распараллеленные библиотеки:
Решение систем линейных уравнений
Решение систем линейных уравнений более сложная задача. Здесь есть множество математических методов. Не все работают одинаково хорошо во всех возможных случаях. Методы делят на прямые и итерационные. Соответсвенно и библиотеки для решения систем линейных уравнений я разделяю по этому признаку. Многие из этих библиотек используются как в свободных, так и в коммерческих программах.
  • Прямые методы
    • UMFPACK
    • SuperLU
    • TAUCS (библиотека включает и итерационные алгоритмы)
  • Итерационные методы
    • Многие методы могут быть легко реализованы самостоятельно, см. книжку Templates for the solution of linear systems: building blocks for iterative methods
    • PETSc (возможность распараллеливания по MPI)
    • LASPACK (включает многосеточные методы, но годится только для последовательных машин)
    • TAUCS (библиотека включает и прямые алгоритмы)
    • Aztec (библиотека для параллельного итерационного решения линейных систем, эффективная, с доступным исходным кодом, но несвободной лицензией)
Работа с (разреженными) матрицами
Особенностью решения уравнений в частных производных — необходимость решать системы линейных уравнений с очень большим числом переменных, но при этом соответствующие матрицы имеют большое количество нулевых элементов (являются разреженными). Практически любой расчёт станет невозможным, если хранить все эти нулевые элементы в памяти компьютера. Соответственно, очень важна способность программного обеспечения эффективно работать именно с разреженными матрицами (хранить в памяти только ненулевые элементы). В большинстве языков программирования это достигается использованием специальных библиотек:
  • Fortran
  • C
  • C++ (часто предоставляется более удобный и наглядный синтаксис операций)
    • TNT (просто и сердито, один inlcude-файл)
    • FLENS (включает также эффективный, удобный и элегантный интерфейс к BLAS и LAPACK)
    • uBLAS (интерфейс к BLAS из коллекции библиотек Boost)
    • GMM++ (предоставляет единый интерфейс к разным решателям, успешно используется в GetFEM++)
    • Blitz++ (вообще говоря, не поддерживает разреженные матрицы, но это очень эффективная библиотека, если нужны плотные многомерные матричные структуры, но без линейной алгебры)
    • Seldon (не пробовал)
    • SparseLib++ (не пробовал)
    • + всё то же самое, что и в C
  • Python
Ознакомьтесь также со сравнением производительности C++-библиотек для работы с разреженными матрицами, если вас интересуют вопросы быстродействия.

Прикладные программные пакеты и библиотеки

Переходим к решению собственно систем уравнений в частных производных. Три наиболее используемых математических метода: метод конечных элементов, метод конечных объёмов и метод конечных разностей.

Именно так я и сгруппирую программные пакеты: по типу реализованного математического метода. После имени пакета указаны его основные особенности, такие как размерность задачи на которую он рассчитан или язык программирования с которым он может применяться.

Метод конечных элементов (FEM):
Elmer
1-2-3D, проект рассчитаный на решение задач из разных областей физики: теплопроводности, гидродинамики, механики твёрдого тела, акустики, электромагнетизма, квантовой механики; задачи описываются в виде легко читаемых текстовых файлов, есть неплохой графический интерфейс, поддерживает распараллеливание по MPI, лицензия GPL
FreeFEM++
2D, свой язык программирования транслируемый в C++, типизированный C-подобный, со встроенными типами триангуляций и пространств конечных элементов, код получается понятен, краток и приближен к математической записи задачи в слабой форме — но поддерживаются только треугольные элементы (включая DG- и мини-элементы), хорошая документация, много примеров использования на разных задачах, кроссплатформенный инструмент, лицензия LGPL
FreeFEM3D
3D вариант FreeFEM++, с другими разработчиками, но со схожей идеологией, на сегодняшний день с несколько меньшей фукнциональностью, поддерживает конструктивное описание геометрии задачи
GetDP
1-2-3D, формальное описание проблемы с помощью специального языка, приближенное к математической формулировке, в некотором смысле идеологически близок FreeFEM++, может решать интегро-дифференциальные задачи, в данный момент заточен под задачи из области электромагнетизма, акустики, теплопроводности и механики, ищут добровольцев готовых применить GetDP в области гидродинамики, лицензия GPL
Impact
3D, пакет для расчётов методом конечных элементов упругих и упругопластичных деформаций при ударах, написан на Java, имеет графический интерфейс, лицензия GPL, для визуализации полагается на несвободный, но бесплатный для академичекого использования, GiD
Code_Aster
1-2-3D, очень большой (миллион строк кода, более 360 разных конечных элементов) пакет для расчётов задач механики сплошных сред, термо- и гидродинамики, акустики и магнетизма и других, заметна ориентация проекта на инженерные приложения, поддерживается язык программирования Python, лицензия GPL, документация преимущественно на французском языке
Deal.II
1-2-3D, библиотека для C++, получила в 2007 году премию Вилкинсона, хорошая документация, локальная адаптация сеток, p- и hp- методы, встроенные средства создания сеток, автоматическое распараллеливание сборки линейной системы и других операций на многоядерных/многопроцессорных машинах (SMP), поддержка кластерного параллелизма (MPI), но выбор элементов беднее, чем в GetFEM++, лицензия QPL
FETK
2D-3D, набор объектно-ориентированных библиотек Си, ориентирован на решение эллиптических уравнений, поддерживает адаптивные сетки и предлагает необычный способ распараллеливания решения (помимо MPI), можно использовать все возможности из bash-подобной оболочки (интерпретатора), есть упрощённая 2D версия для matlab, лицензия GPL
Dolfin/FEniCS
С++ и Python интерфейсы к системе решения задач FEniCS, хорошая поддержка в Debian и Ubuntu, код приближен к математической постановке задачи в слабой форме, но получается длиннее, чем в FreeFEM++, в силу того, что Python язык универсальный; вообще под зонтиком FEniCS объединено сразу несколько интересных проектов
GetFEM++
1-2-3-…-ND, библиотека для C++, есть интерфейсы высокого уровня для Matlab и для Python (!), поддерживает большое количество типов конечных элементов, включая экзотичные, вроде X-FEM, практически любой размерности, есть возможность программирования типовых задач с помощью готовых «кирпичиков», избегая явной сборки линейной системы, отсутствуют встроенные средства создания сеток, можно пользоваться внешними, библиотека кроссплатформенна
LibMesh
1-2-3D, библиотека для C++ с возможностью локальной адаптации сеток, параллельное решение линейных систем с помощью PETSc (MPI), поддерживает безматричные методы, выбор элементов шире, чем в Deal.II
LifeV
2D-3D, C++, основные области применения: гидродинамика, теплопроводность, перенос массы и взаимодействие жидкость–структура в пористых средах
Ofeli
2D-3D, библиотека C++, среди примеров есть задачи теплопроводости, решения уравнения Навье–Стокса для несжимаемой жидкости, теории упругости (2D и 3D), электромагнетизма, лицензия GPL
Rheolef
1-2-3D, библиотека для C++, код получается краток и приближен к математической записи задачи в слабой форме, автоматическая адаптация сеток для 2D задач
MODULEF
довольно продвинутая библиотека для Fortran77
FEATFLOW
2D-3D, библиотеки для Fortran, пакет ориентирован на решение уравнений Навье–Стокса для течения несжимаемых жидкостей, лицензия типа BSD
OpenFEM
довольно продвинутая библиотека для Matlab и Scilab, но версия для свободного Scilab развивается менее активно
Mélina
2D-3D, библиотека для Fortran, документирована исключительно на французском языке
FEAPpv
библиотека для Fortran, для задач теории упругости и теплопроводности, распространяется бесплатно и в качестве приложения к книге, но лицензия неясна, является урезанной версией несвободной библиотеки FEAP
ALBERTA-FEM
1D-2D-3D, библиотека для C, адаптивные сетки, контроль невязок, лицензия GPL, но на данный момент несвободная документация (для старой версии — книжка на Amazon). Release candidate новой версии 3.0 можно найти здесь, там же и черновик книжки к ней (без права копирования).
Метод конечных объёмов (FVM):
FiPy
библиотека для Python, удобная запись задачи, приближенная к математической записи в сильной форме, получается простой и краткий код, решает задачи типа реакция–диффузия–конвекция в 1-2-3D, но не работает с областями со сложной геометрией, библиотека кроссплатформенна
Gerris
2D-3D, пакет ориентированный на решение задач вычислительной гидродинамики (несжимаемаемые течения, уравнения Эйлера, Стокса или Навье–Стокса), поддерживает адаптивные сетки, расчёт переноса веществ в жидкости, распараллеливание по MPI, использует метод Volume-of-Fluid для отслеживания границы между жидкостями, постановка задачи описывается в виде графа, геометрия твердых объектов может быть импортирована из приложений CAD и 3D-моделирования, лицензия GPL
OpenFOAM
визуальная среда + библиотека C++, огромный проект, заточен прежде всего под задачи гидродинамики, кроссплатформенный, у меня пока с ним не сложилось
Overture
пакет C++ библиотек для расчётов на сложных и перекрывающихся сетках методами конечных разностей и конечных объёмов, поддерживает MPI, основной упор на гидродинамику и теорию горения. Лицензия несвободная, запрещает коммерческое использование.
Метод конечных разностей (FD):Здесь можно резко упростить себе жизнь: для этого годится любая библиотека, предоставляющая удобный интерфейс для работы с разреженными матрицами и решателями линейных систем. Заполнение матрицы обычно очевидно из используемой численной схемы. Можно порекомендовать следующие комбинации:
  • Python с PySparse
  • C++ с GMM++ или каким-нибудь другим из решателей линейных систем (см. выше)
  • C или Fortran с любым подходящим решателем линейных систем
  • Overture (см. выше)

Универсальные среды для расчётов и прототипирования (замена Matlab)

Помимо специализированных пакетов описанных выше, есть также свободное ПО для «быстрого и лёгкого» программирования расчётов. Производительность в этом случае обычно приносится в жертву лёгкости программирования и широким функциональным возможностям (универсальности). Приспособить их можно и для решения уравнений в частных производных. Из таких универсальных сред я хочу упомянуть:
Python
Просто удобный язык программирования, но в комбинации с возможностями NumPy/SciPy, графическими возможностями matplotlib (pylab) или VTK/MayaVi, вместе с библиотекой PySparse для работы с разреженными матрицами, многими библиотеками для численных расчётов, удобством интерпретируемого языка программирования и интерактивной оболочкой ipython — на сегодня Python это уже довольно серьёзный инструмент вычислителя. Мне нравится вот эта быстрая вводная книжка по его использованию: Practical Scientific Computing in Python. Для решения УрЧП можно использовать GetFEM++, Dolfin/FEniCS или FiPy.
Scilab
Свободная альтернатива Matlab. Активно развивается и спонсируется. Много возможностей. Для решения УрЧП есть OpenFEM.
Octave
Вроде как позиционируется в качестве замены Мatlab, но вот с решением уравнений в частных производных как-то тихо. Я нашёл только очень простенький FEMOCTAVE. В будущем обещают прикрутить решатель из FEniCS.
Хочу, однако, заметить, что если цель стоит именно в решении уравнений в частных производных, и метод нужно написать быстро, то стоит обратить внимание на неуниверсальные, но гибкие и лёгкие в использовании:
  • FreeFEM++/FreeFEM3D
  • GetDP
  • Gerris
Если же программирование задачи надо исключить или свести к минимуму, могут пригодится «графические» среды (я, в данный момент, не могу ничего сказать об их гибкости/эффективности):
  • Elmer
  • Impact
На этом я заканчиваю этот обзор. Я намеренно исключил из обзора программное обеспечение предназначенное для других классов задач. Например, про что я знаю мало и рассказать не могу про R (статистика), среды для символьных вычислений, ПО для анализа и обработки изображений, ПО для кластерного анализа и распознавания образов, ПО для анализа генетических последовательностей (список можно продолжать). Буду рад поставить ссылки на соответствующие обзоры.Дополнение 2008.04.15: добавил в обзор Code_Aster, Elmer, FEATFLOW, FETK, Gerris, Impact, Mélina, Ofeli, Overture. Дополнение 2011.06.30: добавил FLAME, PLAPACK, ScaLAPACK, Elemental и ALBERTA-FEM, исправил битые ссылки.

Смотрите также:
Сравнение программ для построения научных графиков

20 коммент.:

  1. Анонимный25/3/08 18:30

    Можно также добавить:
    http://slffea.sourceforge.net/index.html
    http://endo.sandia.gov/SEACAS/Documentation/SEACAS.html
    http://impact.sourceforge.net/

    ОтветитьУдалить
  2. Спасибо за обзор!

    Я бы ещё добавил добавил maxima (+ фронтенд в виде WxMaxima) в раздел компбайнов с удобным ГУИ.

    Мне этот продукт очень понравился - неплохая замена MathCAD'у.

    Удачи.

    ОтветитьУдалить
  3. Да вы, батенька, мастер обзоры делать! ))
    Огромное спасибо за полезную информацию!

    ОтветитьУдалить
  4. А что скажете на счёт FreeMat? http://freemat.sourceforge.net/ Тоже замена Матлабу, и тоже развивается.
    Из библиотек пользую (хоть и не очень активно) GNU Scientific Library:
    http://www.gnu.org/software/gsl/

    ОтветитьУдалить
  5. maxima, как я понимаю, это система компьютерной алгебры и символьных вычислений, о возможности решать с её помощью УрЧП я не знаю, поэтому в обзор не включал.

    На сайт FreeMAT посмотрел. Спасибо за ссылку. Однако информации о наличии пакетов/функций/библиотек для решения уравнений в частных производных я не нашёл. Если найдёте — буду рад добавить.

    ОтветитьУдалить
  6. Octave это пакет для численных расчётов и операций с матрицами. Скажем так, Октава для решения УрЧП это немного не то. Здесь скорее Maxima будет уместнее.

    Обзор крут, снимаю шляпу.

    ОтветитьУдалить
  7. Обзор хороший, только неплохо было бы еще осветить пре- и пост-процессоры, например gmsh, salome и т.д.
    В моих закладках есть ещё такие ссылки:
    http://ffep.sourceforge.net библиотека FEA на С. Давно обновлялась
    http://www.ofeli.net -- Объектно ориентированная конечно-элементная библиотека (C++)
    http://www.fetk.org
    http://www.csc.fi/elmer -- активно развивается, имеет интерфейс к ANSYS
    https://computation.llnl.gov/casc/Overture
    http://www.opencfd.co.uk -- для решения задач гидродинамики
    http://www.ce.berkeley.edu/~rlt/feap
    http://www.code-aster.org

    ОтветитьУдалить
  8. Скажите, есть опыт использования этих библиотек в коммерческих проектах? Тех же deal.II и libMesh.

    ОтветитьУдалить
  9. 2dmitry:
    Deal.ii насколько мне известно применяется в коммерческих проектах. Про Libmesh сказать не могу. OpenFOAM в прошлом коммерческий продукт, и очевидно, и теперь имеет коммерческих пользователей. Возможно и у другие продукты используются в коммерческих организациях (это не всегда легко выяснить).

    Если же говорить о библиотеках для решения СЛУ, то и UMFPACK, и SuperLU, и TAUCS, и PETSc активно применяются во многих коммерческих проектах и продуктах.



    P.S. Чтобы не забыть: в обзор можно добавить ещё FEATFLOW и Gerris.

    ОтветитьУдалить
  10. 2 jextee
    На их странице написано, что они радыф обсудить условия предоставления коммерческой лицензии, что это означает на практике, вы не обладаете сведениями подобного рода? может, Ваши знакомыне имели с ними по этому поводу дело?

    ОтветитьУдалить
  11. 2dmitry:
    Я не вполне понимаю Ваш вопрос, о каком именно пакете Вы говорите и что именно подразумеваете под коммерческим использованием.

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

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

    Если под коммерческим использованием подразумевается создание собственного ПО на основе выше перечисленного, и распространение его на условиях отличных от условий лицензии, то для этого нужно договариваться с правообладателями. Полагаю, именно таким образом в Matlab/Femlab и Matematica используется UMFPACK.

    К сожалению, ничего более конкретного сказать не могу. Среди моих знакомых нет людей, которые бы разрабатывали коммерческое вычислительное ПО.

    ОтветитьУдалить
  12. Анонимный21/4/08 15:26

    CalculiX забыли (http://www.calculix.de/). Это решатель (ccx) с синтаксисом проприетарного Abaqus-а, а также пре- постпроцессор (cgx).
    Хорошую подборку свободного софта для численного моделирования (CAE и математический софт) включает в себя специализированный дистрибутив линукса - CAELinux (http://www.caelinux.com/CMS/).

    ОтветитьУдалить
  13. 2jextee
    Спасибо за комментарий.
    Вам не приходилось совмещать FEM и BEM с использованием вышеописанных пакетов?

    ОтветитьУдалить
  14. 2анонимный:
    Спасибо. Ссылки на CalculiX и CAELinux поставлю. Тоже недавно нашёл эти проекты, кажется очень интересные, но ещё толком не смотрел.

    Про пре- и постпроцессоры (генераторы сеток и визуализаторы) писать нужно отдельно. В ближайшее время, наверное, не соберусь.

    2Dmitry:
    BEM я никогда не использовал. На сайте GetDP написано, что он поддерживает Boundary Elements Method, но возможность в данный момент экспериментальная и недокументированная.

    ОтветитьУдалить
  15. Анонимный27/4/08 19:18

    Salome - это не пост или препроцессор. Это система интеграции. В Salome-Meca в состав входит пост- и препроцессор, сеточный генератор, решатели Code-Aster и Code_Saturne и т.д.

    ОтветитьУдалить
  16. www.cvmlib.com

    Отличный интерфейс BLAS/LAPACK в С++.

    ОтветитьУдалить
  17. Dude, oh why didn't I bump into your blog 28 hours ago, this would save me at least 27 :)
    Спасибо огромное!

    ОтветитьУдалить
  18. Михаил Артемьев30/6/11 05:12

    Отличный обзор. Можно сюда добавить еще библиотеку Alberta (ранее называлась Albert)

    ОтветитьУдалить
  19. Михаил Артемьев12/9/11 10:05

    Еще вот недавно нашел:
    DUNE, the Distributed and Unified Numerics Environment is a modular toolbox for solving partial differential equations (PDEs) with grid-based methods. It supports the easy implementation of methods like Finite Elements (FE), Finite Volumes (FV), and also Finite Differences (FD).
    http://www.dune-project.org/index.html

    ОтветитьУдалить