Материалы магистров ДонНТУ
- http://masters.donntu.ru/2010/fknt/kucherenosova/diss/index.htm
Тема магистерской работы:«Исследование эффективности параллельных вычислительных систем»
Автор:Кучереносова Ольга
Руководитель: проф.Башков Е.A.
- http://masters.donntu.ru/2010/fknt/mishchuk/diss/index.htm
Тема магистерской работы: «Анализ эффективности вычислительных систем с использованием Марковской модели»
Автор:Мищук Юлия
Руководитель: Фельдман Лев Петрович
- http://masters.donntu.ru/2002/fvti/smagin/diss/index.html
Тема магистерской работы:«MIMD-модель сетевого объекта с сосредоточенными параметрами»
Автор:Смагин Алексей
Руководитель: проф.Святный В.А.
- http://masters.donntu.ru/2005/fvti/gorb/diss/index.htm
Тема магистерской работы: «Решение больших систем линейных алгебраических уравнений в распределенной вычислительной среде»
Автор:Горб Павел
Руководитель: Ладыженский Юрий Валентинович.
- http://masters.donntu.ru/2009/fvti/al-masri/diss/index.htm
Тема магистерской работы: «Параллельные методы решения СЛАУ на вычислительном кластере»
Автор: АльМасри Мохаммед Рида
Руководитель: Ладыженский Юрий Валентинович.
- http://masters.donntu.ru/2009/fvti/nazarenko/diss/index.htm
Тема магистерской работы: «MIMD-симулятор и оптимизатор параллельных моделей дискретных динамических систем»
Автор: Назаренко Кирилл
Руководитель: проф.Святный В.А.
- http://masters.donntu.ru/2007/fvti/kozhuhov/library/gaussThesis.html
Тезисы к докладу «Метод Гаусса решения СЛАУ. Модификации. Варианты распараллеливания»
Авторы: Кожухов А.Е., Фельдман Л.П.
В этом докладе рассматривается метод Гаусса решения систем линейных алгебраических уравнений. Основная цель —
рассмотрение различных модификаций метода исключения Гаусса и вариантов распараллеливания
алгоритма в вычислительной системе с заданной топологией.
Учебники
- http://www.yugzone.ru/x/r-t-yuarson-razryazhennye-matricsy/
Р.Тьюарсон. Разреженные матрицы
Первая в мироввой литературе книга, специально посвященная разреженным матрицам,
-матрицам с большим числом нулевых элементов. В ней в доступной форме излагается
техника применения разреженных матриц в широких классах задач, использующих вычислительные
методы линейной алгебры и математического программирования.
- http://lib.rus.ec/b/165226/download
Писсанецки С. Технология разреженных матриц.
Книга американского специалиста, охватывающая практически все
алгебраические задачи по разреженным матрицам. Представлено много
фактического материала по технологии применения разреженных матриц,
изложение последовательное и наглядное.
- http://www.twirpx.com/signup/
Джордж А., Лю Д., Численные методы решения больших разреженных систем уравнений.
В книге известных американских математиков-вычислителей описаны все основные методы решения разреженных
положительно определенных линейных систем. Впервые в монографической литературе излагаются алгоритмы параллельных
и вложенных сечений, разработанные А. Джорджем и предназначенные для систем метода конечных элементов. Включены
тексты фортранных программ, реализующие описанные методы.
- http://www.yugzone.ru/x/pryamye-metody-dlya-razrezhennykh-matrics/
Эстербрю О., Златев З. Прямые методы для разреженных матриц
Небольшая книга датских специалистов, отражающая опыт разработки программ для разреженных несимметричных систем.
Авторы сосредоточили внимание на «скандинавском» варианте решения задачи, подробно обсуждают возможности его
применения. Много внимания уделено деталям разреженной технологии — динамическим структурам хранения, организации
выбора главного элемента. .
- http://www-users.cs.umn.edu/~saad/PS/iter1.pdf
Yousef Saad. Iterative Methods for Sparse Linear Systems.
Эта книга может быть использована для обучения студентов старших курсов по итерационным методам
для линейных систем. Инженеры и математики найдут его содержание легко доступным,
а специалисты-практики и преподаватели по достоинству оценят ее в качестве полезного ресурса.
Предисловие включает в себя учебные программы, рассчитаные на семестр обучения.
- http://fpmi.ami.nstu.ru/.../umf/MethodsSLE.pdf
М.Ю. Баландин Э.П. Шурина. Методы решения СЛАУ большой размерности
Учебное пособие для студентов. В пособии рассматриваются форматы хранения разреженных матриц и реализация операций над ними, предобуславливание,
классические итерацуионные и проекционные методы на подпространствах Крылова. .
- http://mathc.chat.ru/books/amos0001.htm
Амосов А.А, Дубинский Ю.А, Копченова Н.В. Вычислительные методы для инженеров
В книге рассматриваются вычислительные методы, наиболее часто используемые в практике инженерных и
научно-технических расчетов: методы, решения задач линейной алгебры и нелинейных уравнений, проблема собственных
значений, методы теории приближения функций, численное дифференцирование и интегрирование, поиск экстремумов функций,
решение обыкновенных дифференциальных уравнений. Значительное внимание уделяется особенностям реализации
вычислительных алгоритмов на ЭВМ и оценке достоверности полученных результатов. Имеется большое количество
примеров и геометрических иллюстраций.
- http://window.edu.ru/window_catalog/redir?id=27391&file=m714.pdf
Глушакова Т.Н., Блатов И.А.Методы решения систем с разреженными матрицами. Теория графов: Учебное пособие
Методические указания к спецкурсу по методам решения систем с разреженными матрицами, теории графов,
для студентов 3-го курса дневного и вечернего отделений факультета прикладной математики, информатики и
механики Воронежского государственного университета.
- http://www.vargin.mephi.ru/bookpc/chisl_metod/chislmet_1.rar
Мышенков В.И., Мышенков Е.В.Численные методы.
Учебное пособие содержит изложение основных понятий и методов теории погрешностей,
аппроксимации, численного дифференцирования, вычисления определенных интегралов, решения
нелинейных уравнений, систем линейных и нелинейных уравнений, методов решения задач на собственные
значения.
- www.math.ucsb.edu/~hdc/teaching/Math206D/templates.pdf
Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods.
Электронная версия 2-го издания книги от the Society for Industrial and Applied Mathematics.
Специализированные библиотеки
- http://parallel.ru/tech/tech_dev/par_libs.html
Специализированные параллельные библиотеки
Параллельные процедуры из областей линейной алгебры,сеточных методов, методов Монте-Карло, генетических алгоритмов,
рендеринга изображений, квантовой и молекулярной химии и др., доступные для использования в пользовательских приложениях.
- http://hpcl.cse.msstate.edu/projects/mpi/tools_libraries.html
MPI Related Tools and Libraries
Приведен список инстументов и библиотек, основанных на стандарте MPI и их краткое описание.
- http://www.cs.sandia.gov/CRF/aztec1.html
Аztec
Aztec — параллельная библиотека итерационных методов для решения систем линейных уравнений. Позволяет описывать части распределенной
матрицы с использованием глобальной адресации..
- http://www.netlib.org/scalapack/scalapack_home.html
ScaLAPACK Home Page
Библиотека ScaLAPACK включает подмножество процедур LAPACK, переработанных для использования на MPP-компьютерах, включая: решение систем линейных уравнений,
обращение матриц, ортогональные преобразования, поиск собственных значений и др.
- http://www.mcs.anl.gov/petsc/petsc-as/
PETSc-Portable, Extensible Toolkit for Scientific Computation
Набор процедур и структур данных для параллельного решения научных задач с моделями, описываемыми в виде
дифференциальных уравнений с частными производными.Библиотека реализована с помощью MPI.
- http://glaros.dtc.umn.edu/gkhome/views/metis/
METIS — Family of Multilevel Partitioning Algorithms
METIS это семейство программ для разделения неструктурированных графов и гиперграфов и снижения заполнения разреженных матриц.
Основные алгоритмы, используемые МЕТИС, предназначены для решения задач большой размерности.
- http://www.netlib.org/utk/people/JackDongarra/la-sw.html
Freely available software for linear algebra on the web (April 2009)
Список свободно доступного программного обеспечения для решения задач линейной алгебры для высокопроизводительных
компьютеров.Приведена информация, для какого типа задач предназначено ПО: плотные/разреженные матрицы,прямые и
итерационные методы решения СЛАУ, вычисление собственных значений.
- http://www.netlib.org/utk/papers/iterative-survey/
Victor Eijkhout. Overview of Iterative Linear System Solver Packages
Описание и сравнение нескольких пакетов для итерационного решения систем линейных уравнений.
- http://www.uic.unn.ru/~zny/nl/doc/html/index.html
Библиотека NL - Numerical Library
Библиотека представляет собой пакет функций учебно-исследовательской библиотеки численных методов NL, написанных на языке C.
Статьи и материалы по теме работы
- http://mi.mathnet.ru/rus/mm/v5/i2/p66
А. Б. Кучеров, Е. Ю. Олейник. Прямые методы решения больших разреженных систем уравнений на основе
блочного порядка два разложения матрицы
Рассматриваются алгоритмы переупорядочения разреженной симметричной положительно определенной матрицы к
блочной форме блочного порядка два.Предложен новый алгоритм уравновешенных вложенных сечений с внутренним
QMD-упорядочением. Приводятся результаты численных экспериментов для сеточных задач с 10000–25000 неизвестными,
показывающие, что благодаря предложенному блочному подходу удается достичь 25–30% экономии затрат памяти
без заметного роста числа арифметических операций, требуемых на этапе решения треугольных систем.
- http://ops.rsu.ru/download/works/SparseMatrix.pdf
Б.Я. Штейнберг. Параллельное умножение разреженной матрицы на вектор.
Предлагается алгоритм умножения разреженной матрицы на вектор для параллельных
компьютеров с разделяемой памятью. Рассматриваемый алгоритм модет быт эффективен
при многократном умножении матрицы на вектор.
-
http://dspace.nbuv.gov.ua:8080/dspace/bitstream/handle/123456789/1444/14%20-%20Popov.pdf
А.В. Попов. Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами
Рассматриваются блочные алгоритмы прямых методов исследования и решения систем линейных алгебраических уравнений с
разреженными (ленточными, профильными, блочно-диагональными с окаймлением) симметричными матрицами на компьютерах
MIMD-архитектуры. Исследуется эффективность рассматриваемых алгоритмов. Приводятся некоторые результаты численных
экспериментов на MIMD-компьютере.
- http://www.iai.dn.ua/public/JournalAI_2006_4/Razdel3/21_Popov.pdf
А.В. Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере.
Рассматриваются блочные алгоритмы исследования и решения задач линейной алгебры с
разреженными (узкими ленточными, с окаймлением и т.п.) симметричными матрицами на
компьютерах MIMD-архитектуры. Исследуется эффективность рассматриваемых алгоритмов.
Приводятся некоторые результаты численных экспериментов на MIMD-компьютере.
- http://network-journal.mpei.ac.ru/cgi-bin/main.pl?l=ru&n=12&pa=14&ar=3
А.М. Чернецов, О.Ю.Шамаева. Проблемы параллельной реализации алгоритмов расчета электронной структуры больших молекул на кластерных системах.
Расчеты электронной структуры гигантских молекул являются одними из самых сложных в современной науке и требуют использования высокопроизводительных
вычислительных средств, таких как суперЭВМ и кластерные установки.
- http://omega.sp.susu.ac.ru/books/conference/PaVT2008/papers/Short_Papers/035.pdf
Г.Б. Сушко, С.А. Харченко. Многопоточная параллельная реализация итерационного
алгоритма решения систем линейных уравнений с динамическим распределением нагрузки по нитям вычислений.
В данной работе для решения систем уравнений с неструктурированными разреженными
матрицами большой размерности предлагается вычислять неполное разложение матрицы высокого порядка
точности (ICH2/ILU2) и затем решать систему уравнений с использованием
предобусловленных итерационных алгоритмов типа подпространства Крылова. Приводятся результаты численных экспериментов по
масштабируемости предложенных алгоритмов на многоядерных процессорах для
систем линейных уравнений, возникающих при моделировании задач вычислительной гидродинамики в пакете “FlowVision”.
- http://www.mathnet.ru/php/getFT.phtml?jrnid=mm&paperid=2206&what=fullt
А.Н. Заворин. Параллельное решение линейных систем при моделировании электрических сетей.
Рассматривается параллельная реализация метода Гаусса решения разреженных СЛАУ, возникающих при
расчете электрических цепей. Приводятся примеры применения разработанных методов для решения практических задач .
- http://alglib.sources.ru/sparse/qmr.php
Решение системы линейных уравнений методом QMR
Метод QMR используется для решения системы линейных уравнений с разреженной несимметричной матрицей.
- http://alglib.sources.ru/sparse/gmres.phphttp://alglib.sources.ru/sparse/gmres.php
Решение системы линейных уравнений методом GMRES
Метод GMRES используется для решения системы линейных уравнений с разреженной несимметричной матрицей.
- http://www.iaeng.org/publication/WCECS2009/WCECS2009_pp367-371.pdf
Nisrine Sinno, Hussein Youssef, Ghaddar Ahmad. Performance optimization of Markov models in simulating computer networks.
Эта статья описывает применение дискретных Марковских моделей для моделирования компьютерных сетей с постоянным числом
клиентов. Рассматриваются две модели сети: Гордан-Ньюэлла и Кокс-Кокс.
- http://www.cs.berkeley.edu/~richie/cs267/svd/writeup.html#b3
Ketan Mayer-Patel, Dane Morgan, and Karin Lin: Large Sparse SVD
Рассматривается алгоритм SVD (факторизация) для больших разреженных матриц. Приведено краткое объяснение алгоритма
Ланцоша, а затем подробный последовательный алгоритм.
- http://technomag.edu.ru/doc/55141.html
И. В. Станкевич. Хранение и использование разреженных матриц в конечно-элементной технологии
Рассмотрено хранение и использование разреженных матриц при итерационном решении больших систем линейных
алгебраических уравнений, возникающих в результате применения конечно-элементной технологии как составной части
комплексной автоматизации сквозного цикла: проектирование — конструирование — изготовление.
- http://vestnik.vgasu.ru/attachments/si-3(6)_2(2)_ignatev-6-08.pdf
А.В. Игнатьев, В.Н. Ромашкин. Анализ эффективности методов решения больших разреженных
систем линейных алгебраических уравнений
Рассмотрены эффективные методы для решения больших разреженных систем линейных
алгебраических уравнений, возникающих при применении метода конечных элементов (МКЭ)
к расчету строительных конструкций. Данная работа ограничена рассмотрением прямых методов решения для симметричных положительно определенных систем уравнений.
- http://www.hse.ru/data/049/621/1235/003.pdf
Авдошин С.М., Савельева А.А. Алгоритм решения систем линейных уравнений в кольцах вычетов.
Разработан эффективный алгоритм решения систем линейных уравнений в кольцах вычетов, эквивалентный по сложности известному
алгоритму решения систем в полях Галуа. Приведены результаты сравнительного анализа предложенного алгоритма
и существующих аналогов на основе асимптотической оценки их временной сложности.
- http://www.iai.dn.ua/public/JournalAI_2006_4/Razdel3/20_Popov.pdf
В.С. Зубатенко, А.С. Майстренко, И.Н. Молчанов, В.В. Полянко, А.В. Попов,
О.В. Рудич, А.Н. Химич, Т.В. Чистякова. Исследование некоторых параллельных
алгоритмов решения задач линейной алгебры на MIMD-компьютерах
Рассматриваются некоторые параллельные циклические алгоритмы исследования и решения задач
линейной алгебры на MIMD-компьютерах. Исследуется эффективность распараллеливания.
Приведены результаты численных экспериментов на MIMD-компьютерах кластерного типа.
- http://dspace.nbuv.gov.ua:8080/dspace/bitstream/handle/123456789/1592/22-Lastovchenko.pdf
А.Н. Химич, А.В. Попов, Т.В. Чистякова, О.В. Рудич, Т.А. Герасимова. Исследование блочно-циклических алгоритмов на семействе кластеров СКИТ.
Рассмотрены некоторые особенности создания циклических алгоритмов для параллельных компьютеров и тенденции их
развития. Проведены исследования блочно-циклических алгоритмов решения задач линейной алгебры на примере библиотеки
программ ScaLAPACK, функционирующей на семействе компьютеров СКИТ, разработанном в Институте кибернетики им. В.М.
Глушкова НАН Украины.
- http://www.ecn.purdue.edu/ParaMount/ATune/2008ICS_ATune.pdf
Seyong Lee and Rudolf Eigenmann. Adaptive Runtime Tuning of Parallel Sparse Matrix-Vector
Multiplication on Distributed Memory Systems.
Умножение разреженной матрицы на вектор (SpMV) — широко используемая операция, которая, как правило,выполняется в цикле
большое количество раз. Представлены механизмы настройки выполнения для улучшения
параллельного выполнения на системах с распределенной памятью. Фактические эксперименты на 26 вещественных матрицах показывают, что время выполнения снижается до 68,8% (30,9% в среднем) на базе
блок-распределенных параллельных алгоритмов на распределенных системах с 32 узлами.
- http://www.mendeley.com/research/parallel-monte-carlo-algorithms-sparse-slae-using-mpi/
V. Alexandrov and A. Karaivanova. Parallel Monte Carlo Algorithms for Sparse SLAE Using MPI.
Представлена проблема решения разреженных систем линейных алгебраических
уравнений (СЛАУ) параллельным численным методом Монте-Карло.
Рассмотрен почти оптимальный алгоритм метода Монте-Карло.
- http://num-meth.srcc.msu.su/zhurnal/tom_2000/pdf/art1_4.pdf
Г.А. Тарнавский, С.И. Шпак. Схема распараллеливания операций решения систем алгебраических уравнений
методом многомерной скалярной прогонки.
Предлагается ряд схем распараллеливания операций, позволяющих перенести алгоритмы, эффективно
использовавшиеся для широкого класса научных и прикладных задач аэродинамики, в область новых компьютерных
технологий с использованием высокопроизводительных многопроцессорных вычислительных систем. Рассмотренные схемы
могут быть непосредственно реализованы на многопроцессорных вычислительных системах с общей памятью.
- pmaa06.irisa.fr/papers_copy/Boman.pdf
Erik G. Boman. Combinatorial Algorithms for Parallel Sparse Matrix Distributions.
Комбинаторные алгоритмы давно играют важную стимулирующую роль в
параллельных вычислениях. Важной проблемой в вычислениях разреженных матриц является
распределение разреженных матриц и векторов между процессорами. Представлены результаты с
использованием параллельной разметки с использованием инструментария Золтана, который способен
эффективно разделять очень большие объемы данных множеств (матриц).
- www.math.uu.nl/people/bisseling/Mondriaan/4-40901.pdf
Brendan Vastenhouw, Rob H. Bisseling. A Two-Dimensional Data Distribution Method for
Parallel Sparse Matrix-Vector Multiplication.
Представлен новый 2-мерный метод разделения данных в разреженных умножения матрицы
на вектор. Эксперименты показали сокращение объема передач данных по сравнению с
одномерным методом, и в целом хороший баланс нагрузки по передачам данных.
- www.informatics.org.cn/doc/ucit200908/ucit20090810.pdf
FU Chao-jiang. Parallel solution for finite element linear systems of equations on workstation cluster.
В работе рассматривается параллельный алгоритм PCGM
и его реализация на кластере рабочих станций DELL.
Подробно анализируется схема хранения. Эксперимент показывает, что разработанный параллельный
алгоритм имеет высокое ускорение и хорошие показатели
эффективности на высокопроизводительном кластере.
- http://portal.acm.org/citation.cfm?id=256544
Anshul Gupta George Karypis and Vipin Kumar. A Highly Scalable Parallel Algorithm for Sparse Matrix
Factorization.
Описывается масштабируемый параллельный алгоритмов для факторизации разреженных матриц,
анализируется их эффективность и масштабируемость, а также представлены экспериментальные результаты
до 1024 процессоров на компьютере Cray T3D. В рамках анализа и экспериментальных результатов,
показывается, что алгоритм существенно улучшает состояние дел в области параллельных прямых
методов решения разреженных линейных систем -как с точки зрения масштабируемости, так и общую производительность.
- dx.doi.org/10.1137/S089547980139604X
Anshul Gupta.Improved Symbolic and Numerical Factorization
Algorithms for Unsymmetric Sparse Matrices (IBM Research Report).
Представлены алгоритмы для символьной и числовой факторизации в
прямых методах решения систем линейных уравнений с разреженными несимметричными матрицами.
Приводятся экспериментальные результаты, чтобы продемонстрировать достоинства нового алгоритма.
- www.hpca.uji.es/ficheros/badia/tr_parco05.pdf
J. Aliaga, F. Almeida, J.M. Bad , S. Barrachina, V. Blanco, M. Castillo, R. Mayo,
E.S. Quintana, G. Quintana, C. Rodriguez, F. de Sande, A. Santos. Parallelization of GSL
on Clusters of Symmetric Multiprocessors.
В этой статье обсудается применение гибридной парадигмы программирования, которая объединяет интерфейс
передачи сообщений (MPI) с общей памятью программ (OpenMP). Эта модель используется для
параллельного решения двух основных задач: вычисления разреженного матрично-векторного произведения и
динамического программирования. Сравниваются результаты гибридной модели с применением pureMPI
на кластере двухъядерных процессоров Intel Xeon. Экспериментальные результаты показывают, что поведение
модели зависит, среди прочих факторов, от приложения и размера задачи.
- www.sandia.gov/~egboman/papers/PARA08.pdf
Michael M. Wolf, Erik G. Boman, and Bruce A. Hendrickson. Optimizing Parallel Sparse Matrix-Vector
Multiplication by Corner Partitioning
Умножение вектора разреженной матрицы является важной операцией
в научных вычислениях. Предлагается оптимизировать
параллельное выполнение этой операции за счет снижения пересылок данных.
Дается обзор существующих подходов и представлен новый 2-мерный
метод для разделения симметричных матриц.
Метод прост и может быть реализован с использованием существующего программного обеспечения
для топологии гиперграф. Результаты экспериментов показывают, метод предлагает
лучшее качество, чем традиционный одномерный
и конкурентоспособен с двумерными методами.
- informatik.unibas.ch/research/_Downloads/fgcs03.pdf
Olaf Schenk, Klaus Gartner. Solving unsymmetric sparse systems of linear equations with PARDISO.
Описываются новые методы для разделения несимметричных матриц с полной
блочно-диагональной структурой, которые были включены в последние версии PARDISO. Эксперименты показывают, что высокая
производительность последовательно достигается при больших разреженных несимметричных матриц из реальных приложений.
Дополнительные ресурсы
- http://technomag.edu.ru/index.html
Электронное научно техническое издание «Наука и образование»
Журнал выпускается с ноября 2003 года в ежемесячном формате с дополнением блоком новостей, форумом и доской объявлений
в режиме on-line. В журнале публикуются статьи по следующим темам/рубрикам:
- Общие проблемы инженерного образования
- Наука в образовании: электронное издание
- Cals-технологии
- Открытое образование
- Из истории технического прогресса
- Инженер в современной России
- Будущему инженеру
- Зарубежное образование
- http://www.mathworks.com/access/helpdesk/help/pdf_doc/otherdocs/simax.pdf
John R. Gilbert,Cleve Moler, Robert Schreiber.Sparse Matrices in Matlab: designand implementation
Расширение среды Matlab для работы с разреженными матрицами. Описаны дополнения для хранения и операции над разредженными матрицами.
- www.springerlink.com/index/yu328600152x8t12.pdf
Patrick R. Amestoy, Iain S. Duff, Daniel Ruiz. A Parallel Matrix Scaling Algorithm.
Предложены итерационные процедуры и способы их эффективного распараллеливания. Изучена эффективность параллельной реализации в нескольких вычислительных средах.
- http://plakhov.livejournal.com/85583.html?thread=1387599
Зачем в Яндексе перемножать разреженные матрицы
Например, для того, чтобы автоматически искать синонимы. Очень интересная и познавательная
статья о практическом применении численных методов в "обычной" жизни.
