обзор мат.пакетов, "позволяющих" решать СЛАУ

[KSergP]

Подскажи мат. пакеты в которых реализована возможность решения СЛАУ с ПЛОТНОЙ матрицей итерационными меодами крыловского типа. (BiCGStab,GMRES, QMR и др.).

[Vassil]

Несколько раз в нашем Форуме приводилась ссылка по линку:

http://fpmi.ami.nstu.ru/arhive/courses/ ... odsSLE.pdf

на учебное пособие "Методы решения СЛАУ большой размерности", М.Ю.Баландин и Э.П.Шурина

Мне кажется, что разделы 4 и 5 могут помочь Вам.

[KSergP]

собственно сделал вот такой обзор....
хотел спросить мнения "окружающих" на предмет его корректности....

одно осталось понятым не до конца, это пакет LAPACk....
он вообще реализует итерационные методы (если да, то какие) или же он ориентирован на прямые??????


1.ATLAS (Automatically Tuned Linear Algebra Software) – оптимизированная библиотека, включающая реализацию процедур BLAS и часть функциональности LAPACK;
2.AZTEC – библиотека параллельных подпрограмм для решения больших систем линейных алгебраических уравнений с разреженными матрицами;
3.BLAS (Basic Linear Algebra Subprograms) – библиотека высококачественных процедур, «строительными блоками» для которых являются вектора, матрицы или их части. Уровень 1 BLAS используется для выполнения операций вектор-вектор, уровень 2 BLAS – для выполнения матрично-векторных операций, наконец, уровень 3 BLAS – для выполнения матрично-матричных операций. Поскольку программы BLAS являются эффективными, переносимыми и легко доступными, они используются как базовые компоненты для развития высококачественного программного обеспечения для задач линейной алгебры. Так были созданы широко известные пакеты LINPACK, EISPACK, которые затем были перекрыты пакетом LAPACK, получившим большое распространение. Перечисленные пакеты разработаны на языке Fortran;
4.BLACS (Basic Linear Algebra Communication Subprograms) – набор базовых коммуникационных процедур линейной алгебры, созданных для линейной алгебры. Вычислительная модель состоит из одномерной или двумерной решетки процессов, где каждый процесссодержит часть матрицы или вектора. BLACS используется как коммуникационный слой проекта ScaLAPACK, который переносит библиотеку LAPACK на машины с распределенной памятью;
5.BlockSolve95 – параллельная библиотека для решения разреженных систем линейных уравнений;
6.BPKIT2 – пакет блочных способов предобусловливания, ориентированных на разреженные матрицы;
7.CAPSS – пакет для параллельного решения разреженных линейных систем;
8.CXML (The Compaq Extended Math Library) – расширенная математическая библиотека, включающая в себя часть функциональности BLAS, LAPACK, Direct Sparse Solvers и Iterative-solvers;
9.Direct Sparse Solvers – пакет программ для решения разреженных систем прямыми методами;
10.EISPACK (Eigensystem Package) – пакет программ решения алгебраической проблемы собственных значений;
11.Expokit – пакет программ для решения не больших СЛАУ с плотной матрицей и больших разреженных систем;
12.ILUPACK – библиотке, содержащая способы предобусловливания, ориентированная на разреженные СЛАУ. Пакет включает реализацию процедур BLAS, SPARSEKIT. Реализована на языке С и Fortran;
13.IML++ (Iterative Methods Library) – библиотека итерационных методов решения разреженных СЛАУ, позволяющая использовать несколько простых способов предобусловливания. Пакет включает часть BLAS и MV;
14.Intel MKL (Intel Math Kernel Library) включает несколько стандартных библиотек для высокопроизводительных системах (BLAS, LAPACK и FFTPACK – подпрограммы быстрого преобразования Фурье);
15.IOMDRV – пакет подпрограмм для решения симметричных и несимметричных линейных систем методами крыловских подпространств;
16.Iterative-solvers – пакет подпрограмм решения разреженных систем итерационными методами;
17.ITL (Iterative Template Library) – библиотека программ итерационных методов и способов предобусловливания, являющаяся составной частью MTL.
18.ITPACK (Iterative Package) – пакет программ для решения разреженных систем итерационными методами;
19.ITSOL (The New Sparskit Preconditionning Module) – пакет, содержащий способы предобусловливания, ориентированные на разреженные матрицы. Является составной частью пакета SPARSKIT;
20.JAMA/C++ – библиотека для решения СЛАУ прямыми методами;
21.LAPACK (Linear Algebra Package) – набор реализаций «продвинутых» методов линейной алгебры. LAPACK содержит процедуры для решения систем линейных уравнений, задач нахождения собственных значений и факторизации матриц. Обрабатываются заполненные и ленточные матрицы, но не разреженные матрицы общего вида. Во всех случаях можно обрабатывать действительные и комплексные матрицы с одиночной и удвоенной точностью. Процедуры LAPACK построены таким образом, чтобы как можно больше вычислений выполнялось с помощью обращений к BLAS с использованием всех его трех уровней. Вследствие крупнозернистости операций уровня 3 BLAS, их использование обеспечивает высокую эффективность на многих высокопроизводительных компьютерах, в частности, если производителем создана специализированная реализация. ScaLAPACK является успешным результатом переноса пакета LAPACK на системы с передачей сообщений. Но в таких системах необходимы процедуры, обеспечивающие обмен данными между взаимодействующими процессами. Для этого в ScaLAPACK используется библиотека BLACS;
22.Laspack – пакет программ для решения разреженных систем итерационными методами;
23.LGSOLV – библиотека для решения СЛАУ прямыми методами;
24.LINPACK (Linear Package) – пакет программ решения систем линейных алгебраических уравнений и линейной задачи наименьших квадратов прямыми методами;
25.LinPar – пакет предназначенный для решения плохообусловленных СЛАУ, включая прямоугольные. Если для решения задачи необходимо предобусловливание СЛАУ, то оно выполняется отдельно и методы применяются к уже предобусловленной системе. Соответственно, по окончании процесса решения найденный вектор должен быть пересчитан согласно выполненному предобусловливанию. В схемы методов эти процедуры не включаются;
26.MET (Matrix Expression Templates) – реализованная на языке C++ программа для инженеров и научных работников;
27.MINOS – пакет подпрограмм решения больших разреженных задач линейного и нелинейного программирования;
28.MTL (The Matrix Template Library) – реализованная на языке C++ библиотека базовых операций линейной алгебры, позволяющая решать СЛАУ с разреженными матрицами итерационными методами с предобусловлмванием, за счет включенного пакета ITL;
29.MV++ – небольшая библиотека, содержащая базовые операции линейной алгебры. Данный пакет часто является составной частью более крупных и высокопроизводительных библиотек;
30.ParPre – пакет параллельных версий способов предобусловливания, ориентированных на разреженные матрицы, являющийся составной частью PETs;
31.Parallel Algorithms Project – пакет параллельных версий итерационных методов Крыловского типа для решения разреженных систем;
32.PASVA – пакет подпрограмм решения разреженных систем с блочно-двухдиагональной структурой;
33.PBLAS – Параллельные версии базовых процедур линейной алгебры (BLAS) ;
34.PCGPAK (Preconditioned Conjugate Gradient PAcKage) – пакет программ для решения симметричных и несимметричных разреженных линейных систем методом сопряженных градиентов;
35.PIM (The Parallel Iterative Methods) – набор процедур на Фортран-77, реализующих параллельные версии различных итеративных методов решения разреженных систем линейных уравнений;
36.PSparselib (A Portable Library of Parallel Sparse Iterative Solvers) – библиотека параллельных итерационных методов для разреженных линейных систем;
37.PSPASES (Parallel Sparse Symmetric Direct Solver) – библиотека параллельных версий прямых методов для решения симметричных линейных систем;
38.RALAPACK – пакет подпрограмм для различных операций с разреженными матрицами;
39.ScaLAPACK (Scalable LAPACK) – параллельная версия LAPACK. Широкий набор подпрограмм для решения стандартных задач линейной алгебры;
40.SIRSM – пакет подпрограмм для решения разреженных несимметричных линейных систем;
41.Software Iterative Methods: GMRESR and BiCGstab(ell) – пакет прогамм решения больших разреженных систем с несимметричной матрицей;
42.SPAI (Sparse Approximate Inverse Preconditioner) – пакет способов предобусловливания, ориентированных на разреженные матрицы;
43.SPARKS – пакет подпрограмм для решения разреженных линейных систем в полунеявных методах Рунге-Кутта численного интегрирования систем обыкновенных дифференциальных уравнений;
44.SparseLib++ – библиотка, реализованная на языке C++, позволяющая решать разреженные СЛАУ итерационными методами с предобусловливанием. Включает часть процедур BLAS и IML;
45.SPARSKIT – мощный пакет для решения разреженных СЛАУ итерационными методами с предобусловливанием. Библиотека реализованна на языке Fortran;
46.SPARSPAK (Sparsee Iinear Equations Package) – пакет программ решения разреженных систем линейных алгебраических уравнений с симметричными положительно определенными матрицами;
47.SPLIB – библиотека, позволяющая решать СЛАУ с разреженной матрицей итерационными методами с предобусловливанием, реализованная на языке Fortran;
48.SPLP (Sparse Linear Programming Subprogram) – пакет программ решения задач линейного программирования;
49.SPOOLES – библиотека для решения СЛАУ с разреженной матрицей прямыми методами;
50.SSLES – пакет подпрограмм для решения разреженных несимметричных линейных систем;
51.TCHLIB – пакет подпрограмм для решения симметричных и несимметричных линейных систем методом Чебышева;
52.TNT (Template Numerical Toolkit) – библиотека базовых операций линейной алгебры, ориентированная на разреженные матрицы. Библиотека разработана на языке Fortran;
53.WSMP (Watson Sparse Matrix Package) – пакет программ решения разреженных систем линейных алгебраических уравнений;
54.XMP – пакет подпрограмм для решения задач линейного программирования;
55.YI2M – комплекс программ решения разреженных систем;

[K-3]

Цитата:

пакет LAPACk....
он вообще реализует итерационные методы (если да, то какие) или же он ориентирован на прямые??????

LAPACK реализует только прямые методы

[lin]

В обзоре нет ссылки на TAUCS http://www.tau.ac.il/~stoledo/taucs/
Было бы интересно узнать, удолось ли кому-то подключить библиотеку к своей программе.

[IAA]

С успехом использовал пакет SPARSKIT Дж.Саада
http://www-users.cs.umn.edu/~saad/softw ... rskit.html

Написан на фортране 77 и работает, как швейцарские часы.
Реализует в основном метод сопряженных градиентов и его модификации
с предобуславливателями. Не требует дополнительных
библиотек типа blas и т.д.
Очень понятный интерфейс. Главное, все работает.
Самое забавное, что я перевел исходник этого пакета на язык С
с помощью известной утилиты f2c.exe и тоже все работет замечательно.
Many thank to Saad! Good thing.

В списке отсутствует еще один пакет, который я тоже
успешно использовал: UMFPACK Тима Девиса
http://www.cise.ufl.edu/~davis/

Пакет сразу написан на С и реализует прямые методы, которые
работают как кувалда! Тоже очень понятный интерфейс, но
требует дополнительную библиотеку blas.
Но это небольшое затруднение. Я ее всю собрал и очень доволен.
Этот пакет рекомендую для задач, с не очень большим числом неизвестных.
Так, например, для решения несжимаемых ур. Навье-Стокса я ее
использовал на шаге решения ур. Пуассона. С RAM 1 Гиг максимальная
трехмрная сетка была где-то от 70 до 100 тыс ячеек. Больше не влезало из-за
очень больших L и U матриц (хотя и разреженных).
Для LES рачетов это мало. Нужно до миллиона. Поэтому использовал
итерационные методы, а именно SPARSKIT.

Вобщем, рекомендую.

[KSergP]

IAA писал(а):

В списке отсутствует еще один пакет, который я тоже
успешно использовал: UMFPACK Тима Девиса
http://www.cise.ufl.edu/~davis/

спасибо за замечания.
про UMFPACK я встречал упоминания. Помоему он включен в какой-то более "мощный" пакет.

[IAA]

KSergP писал(а):

спасибо за замечания.
про UMFPACK я встречал упоминания. Помоему он включен в какой-то более "мощный" пакет.

Не заметил. По крайней мере, автор, Тим Девис, ничего не пишет об этом.

Хочу упомянуть еще одну интересную библиотечку:

Библиотека NL
http://www.uic.nnov.ru/~zny/nl/doc/html/index.html

Автор - Н.Ю.Золотых из Нижнего Новгорода.
Библиотека скромненькая, но приятная.
Можно рекомендовать студентам для тренировки.

[KSergP]

IAA писал(а):

KSergP писал(а):

спасибо за замечания.
про UMFPACK я встречал упоминания. Помоему он включен в какой-то более "мощный" пакет.

Не заметил. По крайней мере, автор, Тим Девис, ничего не пишет об этом.

Хочу упомянуть еще одну интересную библиотечку:

Библиотека NL
http://www.uic.nnov.ru/~zny/nl/doc/html/index.html

Автор - Н.Ю.Золотых из Нижнего Новгорода.
Библиотека скромненькая, но приятная.
Можно рекомендовать студентам для тренировки.

автор этой библиотеки частенько "отзывается" на этом форуме)

[KSergP]

IAA писал(а):

В списке отсутствует еще один пакет, который я тоже
успешно использовал: UMFPACK Тима Девиса
http://www.cise.ufl.edu/~davis/

хм...яже говорил, что где-то его видел)))
вот что я нашел в описалке матлаба...

Mathematics, MATLAB Version 7.3 (R2006b)
Support for New Versions of AMD, COLAMD, CHOLMOD, UMFPACKMATLAB 7.3 supports new versions of the following libraries:Library NameVersion
Supported in MATLAB 7.3
AMD2.0
COLAMD2.5
CHOLMOD1.1
UMFPACK5.0

если это кому-то еще интересно))

[KSergP]

есть ли у кого описание BLAS, т.е. где написано за счет чего достигается ускорение?

[K-3]

Цитата:

есть ли у кого описание BLAS, т.е. где написано за счет чего достигается ускорение?

За счет использования особенностей архитектуры машины. Принципы изложены, например, в Деммель "Вычислительная линейная алгебра" или Голуб, Ван Лоан "Матричные вычисления"

[XAPI]

Обзор толковый и нужный.Сам делал чтото подобное ,но не в таких масштабах. А вот мне интересно спросить у народа : ктонить использовал паралеленные версии бибилиотек? Решение систем для какого количества неизвестных можно выжать используя /или нет вышеприведенные библиотеки. Понятно ,что 32 винда дает ограничение по памяти (если ничего не путаю в 1 гиг), в 64 попроще:ограничений вродь как нет.

Сам Я пользовал связку ITL + MTL (прикрутил к своей С++ проге, решал на обычной машине с 32 виндой ).Но вот дело в том ,что рано или поздно встает вопрос количества неизвестных , даже использу sparse хранение матриц, не дает нужного результата(((

[Comga]

IAA писал(а):

С успехом использовал пакет SPARSKIT Дж.Саада
http://www-users.cs.umn.edu/~saad/softw ... rskit.html

Так, например, для решения несжимаемых ур. Навье-Стокса я ее
использовал на шаге решения ур. Пуассона. С RAM 1 Гиг максимальная
трехмрная сетка была где-то от 70 до 100 тыс ячеек. Больше не влезало из-за
очень больших L и U матриц (хотя и разреженных).
Для LES рачетов это мало. Нужно до миллиона. Поэтому использовал
итерационные методы, а именно SPARSKIT.

Вобщем, рекомендую.

А ссылки на публикации применения можно привести?
Заранее благодарен!

[Nik_Svan]

K-3 писал(а):

Цитата:

есть ли у кого описание BLAS, т.е. где написано за счет чего достигается ускорение?

За счет использования особенностей архитектуры машины. Принципы изложены, например, в Деммель "Вычислительная линейная алгебра" или Голуб, Ван Лоан "Матричные вычисления"

За счет использования блочных методов.