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

Хочу предложить небольшой обзор свободного программного обеспечения для численных расчётов. Прежде всего для решения систем уравнений в частных производных (УрЧП). Решать их нужно во многих инженерных и начных областях (в гидродинамике, теории упругости, теплопроводности, электромагнетизме и других). К счастью, в этой области написано много качественных свободных программ. И учитывая, что 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++-библиотек для работы с разреженными матрицами, если вас интересуют вопросы быстродействия.

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

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

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

Метод конечных элементов (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, исправил битые ссылки.

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

Как включить VGA-выход на проектор (используя xrandr)

Не прошло и месяца с тех пор, как мне пришлось подключать ноутбук с видеокарточкой Nvidia к проектору, как пришлось подключать к проектору и свой ноутбук, со встроенным видео Intel 915GM. В этот раз всё было гораздо проще. Рецепт ниже. Насколько я понимаю, он подходит и для большинства владельцев ноутбуков с видео ATI.

В общем, самым простым и универсальным способом мне показалось использование утилиты xrandr, позволяющей управлять видеовыходами и их видеорежимами на лету. Насколько я понимаю, для этого достаточно, чтобы в системе был установлен более-менее свежий X.org и видеодрайвер с поддержкой расширения RandR (Resize and Rotate).

Чтобы посмотреть какие видеовыходы и видеорежимы доступны, нужно выполнить команду xrandr -q:

~$ xrandr -q
Screen 0: minimum 320 x 200, current 1280 x 800, maximum 1280 x 1280
VGA disconnected (normal left inverted right)
LVDS connected 1280x800+0+0 (normal left inverted right) 331mm x 207mm
1280x800 60.0*+ 60.0
1280x768 60.0
1024x768 60.0
800x600 60.3
640x480 59.9
TV disconnected (normal left inverted right)

Как видно, в данный момент у меня включен только основной экран ноутбука (LVDS) в режиме 1280×800, VGA выход на проектор отключен.

Чтобы включить тот или иной режим на том или ином выходе можно использовать команду:

$ xrandr --output название_выхода --mode порядковый_номер_или_описание_режима

Чтобы отключить видео выход:

$ xrandr --output название_выхода --off

Теперь о подключении к проектору. Проекторы в большинстве случаев рассчитаны на вполне определённое разрешение. Чаще всего 1024×768. Совсем старые могут быть 800×600. Прошу заметить, что это разрешение отличается от разрешения распространённого нанче широкого ноутбучного экрана с соотношением сторон 16:10. Я же предпочитаю видеть на экране ноутбука во время презентации то же изображение, что и на проекторе. Это значит, что прежде чем подключать ноутбук к проектору, необходимо переключить разрешение на экране ноутбука, а затем включить вывод идентичного изображения на VGA. При этом изображение на ЖК-экране ноутбука станет замыленным, но это нормально и связано с интерполяцией разрешения 1024×768 на физическую матрицу 1280×800. Вести презентацию это не мешает. После же презентации нужно отключить внешний VGA-выход и вернуть экранное разрешение к нормальному.

В результате я написал себе два однострочных скрипта, чтобы включить «режим презентации»:

xrandr --output LVDS --mode 1024x768 && xrandr --output VGA --mode 1024x768

и чтобы вернутья в нормальный видео-режим:

xrandr --output VGA --off && xrandr --output LVDS --mode 1280x800

Вызывать их можно из терминала, или по кнопке на панели, или по комбинации клавиши (например, с помощью xbindkeys). Это уже детали.

Ссылки по теме (по-английски):
☙ How to use Linux laptop in presentations
☙ Use XRandR 1.2 to Swtich on External Display for Thinkpad Laptop
☙ Xorg RandR 1.2 (в ThinkWiki)
☙ How to use RandR 1.2 (в Debian Wiki)

Изменение межстрочного интервала в LaTeX

После почти трёхнедельного перерыва я наконец более-менее освободился и могу возобновить свои записи в блог:) Сегодня я достаю из черновиков и публикую описание двух способов изменить межстрочный интервал в LaTeX.

Итак, простой способ:

% в преамбуле, чтобы использовать полуторный интервал
\renewcommand{\baselinestretch}{1.5}

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

% в преамбуле
\usepackage{setspace}
\onehalfspacing % полуторный интервал для всего текста
% или \singlespacing % одиночный интервал для всего текста
% или \doublespacing % двойной интервал для всего текста
% или \setstretch{множитель} % произвольный интервал
...

% в тексте
\begin{onehalfspace}
фрагмент текста с полуторным межстрочным интервалом
\end{onehalfspace}
\begin{doublespace}
фрагмент текста с двойным межстрочным интервалом
\end{doublespace}

В общем, можно использовать следующие окружения из setspace меняют межстрочный интервал для фрагмента текста: singlespace, onehalfspace, doublespace, spacing (требует параметра). А команды \singlespacing, \onehalfspacing, \doublespacing и \setstretch{множитель} в преамбуле меняют межстрочный интервал всего документа в целом.