Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки

16+

Название статьи

НОВЫЙ РЕШАТЕЛЬ ДЛЯ АЛГЕБРАИЧЕСКИХ СИСТЕМ РАЗРЕЖЕННЫХ ЛИНЕЙНЫХ УРАВНЕНИЙ С СИММЕТРИЧНОЙ ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННОЙ МАТРИЦЕЙ

Номер журнала	5
Дата выпуска	2012

Тип статьи	научная статья	Коды УДК	519.612: 004.4
Страницы	376-384	Ключевые слова	решение разреженных систем линейных уравнений, разреженные матрицы, супернодальный подход, разреженная алгебра

Авторы

Козинов Евгений АлександровичЛебедев Илья ГеннадьевичЛебедев Сергей АлександровичМалова Анна ЮрьевнаМееров Иосиф БорисовичСысоев Александр ВладимировичФилиппенко Станислав Сергеевич

Место работы

Козинов Евгений Александрович Нижегородский госуниверситет им. Н.И. Лобачевского
Лебедев Илья Геннадьевич Нижегородский госуниверситет им. Н.И. Лобачевского
Лебедев Сергей Александрович Нижегородский госуниверситет им. Н.И. Лобачевского
Малова Анна Юрьевна Нижегородский госуниверситет им. Н.И. Лобачевского
Мееров Иосиф Борисович Нижегородский госуниверситет им. Н.И. Лобачевского
Сысоев Александр Владимирович Нижегородский госуниверситет им. Н.И. Лобачевского
Филиппенко Станислав Сергеевич Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

Представлен новый решатель разреженных СЛАУ с симметричной положительно определенной матрицей. Описана поэтапная схема решения СЛАУ с использованием метода Холецкого. Выполнена последовательная программная реализация представленной схемы на основе супернодального подхода. Реализовано распараллеливание вычислений для систем с общей памятью. Приведены результаты экспериментов, дано их сравнение с результатами, полученными с помощью некоторых известных библиотек.

Загрузить статью

Библиографический список

1 . Davis T.A. Direct methods for sparse linear systems. Philadelphia: SIAM, 2006. 217 p.
2 . George A., Liu J.W.H. An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems // SIAM J. on Numerical Analysis. 1978. Vol. 15, No 5. P. 1053–1069.
3 . Tinney W., Walker J. Direct solutions of sparse network equations by optimally ordered triangular factorization // Proceedings of the IEEE. 1967. Vol. 55, No 11. P. 1801–1809.
4 . George A. Nested dissection of a regular finite element mesh // SIAM J. on Numerical Analysis. 1973. Vol. 10, No 2. P. 345–363.
5 . Джордж А., Лю Дж. Численное решение боль-ших разреженных систем уравнений. М.: Мир, 1984.
6 . Ashcraft C., Liu J.W.H. A partition improvement algorithm for generalized nested dissection // Technical Report BCSTECH-92-020 Boeing computer Services. 1994.
7 . Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // The Bell System Technical J. 1970. Vol. 29. P. 291–307.
8 . Fiduccia C.M., Mattheyses R.M. A linear time heuristic for improving network partitions // 19th IEEE Design Automation Conference, Proceedings. IEEE Press Piscataway, 1982. P. 175–181.
9 . Ashcraft C. Compressed graphs and the minimum degree algorithm // SIAM J. on Scientific Computing. 1995. Vol. 16, No 6. P. 1404–1411.
10 . Hendrickson B., Rothberg. Improving the runtime and quality of nested dissection ordering // SIAM J. on Scientific Computing. 1999. Vol. 20, No 2. P. 468–489.
11 . Liu J.W.H. The role of elimination trees in sparse factorization // SIAM J. on Matrix Analysis and Applications. 1990. Vol. 11, No 1. P. 134–172.
12 . Liu J.W.H. A compact row storage scheme for Cholesky factors using elimination trees // ACM Trans. Math. Software. 1986. Vol. 12, No 2. P. 127–148.
13 . Gilbert J.R., Ng E.G., Peyton B.W. An efficient algorithm to compute row and column counts for sparse Cholesky factorization // SIAM J. Matrix Anal. Appl. 1994. Vol. 15, No 4. P. 1075–1091.
14 . Писсанецки С. Технология разреженных матриц. М.: Мир,1988. Ashcraft C., Grimes R.G., Lewis J.G. et al. Progress in sparse matrix methods for large linear systems on vector supercomputers // International J. of High Performance Computing Applications. 1987. Vol. 1, No 4. P. 10 – 30.
15 . Ng E.G., Peyton B.W. A supernodal Cholesky factorization algorithm for shared-memory multiprocessors // SIAM J. on Scientific Computing. 1993. Vol. 14, No 4. P. 761–769.
16 . Ng E.G., Peyton B.W. Block sparse Cholesky factorization on advanced uniprocessor computers // SIAM J. on Scientific Computing. 1993. Vol. 14, No 5. P. 1034–1056.
17 . Duff I.S., Reid J.K. The multifrontal solution of indefinite sparse symmetric linear equations // ACM Trans. Math. Software. 1983. Vol. 9, No 3. P. 302–325.
18 . Duff I.S., Reid J.K. The multifrontal solution of unsymmetric sets of linear systems // SIAM Journal on Scientific and Statistical Computing. 1984. Vol. 5. P. 633–641.
19 . Liu J.W.H. The multifrontal method for sparse matrix solution: Theory and practice // SIAM Review. 1992. Vol. 34, No 1. P. 82–109.
20 . Liu J.W.H. The multifrontal method and paging in sparse Cholesky factorization // ACM Trans. Math. Softw. 1989. Vol. 15. P. 310–325.
21 . Amestoy P.R., Duff I.S. Vectorization of a multiprocessor multifrontal code // International Journal of Supercomputer Applications. 1989. Vol. 3. P. 41–59.
22 . Amestoy P.R., Duff I.S., L’Excellent J.-Y., Kos-ter J. A fully asynchronous multifrontal solver using dis-tributed dynamic scheduling // SIAM J. on Matrix Ana-lysis and Applications. 2001. Vol. 23, No 1. P. 15–41.
23 . Ashcraft С., Grimes R. The influence of relaxed supernode partitions on the multifrontal method // ACM Trans. Math. Software. 1989. Vol. 15, No 4. P. 291–309.
24 . Demmel J.W., Eisenstat S.C., Gilbert J.R. et al. A supernodal approach to sparse partial pivoting // SIAM J. Matrix Anal. Appl. 1999. Vol. 20, No 3. P. 720–755.
25 . Hogg J.D. Efficient sparse Cholesky factorization. URL: http://www.maths.ed.ac.uk/~s0455378/EfficientCholesky.pdf. Hogg J.D. Elimination Trees and Up-/Down-dating of Sparse Cholesky Factorizations. URL: http:// www.maths.ed.ac.uk/~s0455378/ETreesUpDown.pdf.
26 . Hogg J.D., Reid J.K., Scott J.A. A DAG-based Sparse Cholesky Solver for Multicore Architectures // Tech. report RAL-TR-2009-004, Rutherford Appleton Laboratory. – 2009.
27 . Liu J.W.H., Ng E.G., Peyton B.W. On finding supernodes for sparse matrix computations // SIAM J. on Matrix Analysis and Applications. 1990. Vol. 14, No 1. P. 242–252.
28 . The University of Florida Sparse Matrix Collection. URL: www.cise.ufl.edu/research/sparse/ matrices/.
29 . Karipis G. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices // Technical report, University of Minnesota, Department of Computer Science and Engineering. 2011. URL: http://glaros.dtc.umn.edu/gkhome/fetch/sw/ metis/manual.pdf.
30 . Intel Math Kernel Library Reference Manual. URL: http://software.intel.com/sites/products/documen-tation/hpc/mkl/mklman.pdf.
31 . Li X.S., Demmel J.W., Gilbert J.R. et al. SuperLU Users’ guide // Technical report LBNL-44289. 2011. URL: http://crd-legacy.lbl.gov/~xiaoye/SuperLU/ superlu_ug.pdf.
32 . MUltifrontal Massively Parallel Solver (MUMPS 4.10.0) User’s guide // Technical report ENSEEINT-IRIT. 2011. URL: http://mumps.enseeiht.fr/doc/ user-guide_4.10.0.pdf.