Direct multiplicative methods for sparse matrices. Unbalanced linear systems.

 pdf (473K)  / Annotation

List of references:

  1. Ю. В. Берчун, П. В. Бурков, А. С. Чиркова, С. М. Прокопьева, Д. Л. Рабкин, А. А. Лукьянов. Итерационный метод решения СЛАУ на основе механической аналогии // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2015. — № 08. — С. 14–31.
    • Ju.V. Berchun, P. V. Burkov, A. S. Chirkova, S. M. Prokop'eva, D. L. Rabkin, A. A. Luk'janov. Mechanical Analogy-based iterative method for solving a system of linear equations // Sciens and Education of the Bauman MSTU. Electronic journal. 2015. — no. 08. — P. 14–31. — in Russian.
  2. Ю. М. Брумштейн. Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. — Астрахань: Издательский дом «Астраханский университет», 2004. — № 8. — С. 125–128.
    • Yu. M. Brumshtejn. Use pseudohallucinations formulation in problems of filtration with a free surface // Natural Sciences. — Astrakhan University, 2004. — no. 8. — P. 125–128. — in Russian.
  3. В. М. Вержбицкий. Численные методы. Линейная алгебра и нелинейные уравнения. — М: Издательский дом «ОНИКС 21 век», 2005.
    • V. M. Verzhbickij. Numerical methods. Linear algebra and nonlinear equations. — M: ONYX 21 century, 2005. — in Russian.
  4. В. В. Воеводин. Вычислительные основы линейной алгебры. — М: Наука, 1977.
    • V. V. Voevodin. Computational foundations of linear algebra. — M: Nauka, 1977. — in Russian. — MathSciNet: MR0357426.
  5. В. В. Воеводин, Ю. А. Кузнецов. Матрицы и вычисления. — М: Наука, 1984.
    • V. V. Voevodin, Yu. A. Kuznecov. Matrix and calculations. — M: Nauka, 1984. — in Russian. — MathSciNet: MR0758446.
  6. Б. А. Галанов. О сходимости одного непрерывного метода и его аппроксимаций / Математические методы в кибернетической технике: Сборник. — Киев: Изд-во ИК АН УССР, 1970. — № 7.
    • B. A. Galanov. On the convergence of a continuous method and its approximations / Mathematical methods in cybernetic technology. — Kiev: IR SSR, 1970. — no. 7. — in Russian.
  7. Ф. Гилл, У. Мюррей, М. Райт. Практическая оптимизация. — М: Мир, 1985.
    • F. Gill, U. Mjurrej, M. Rajt. Prakticheskaja optimizacija. — M: Mir, 1985. — in Russian. — MathSciNet: MR0801546.
    • P. E. Gill, W. Murray, H. Margaret. Wright Practical optimization. — System Optimization Laboratory Department of Operations Research Stanford University California, USA. — Academic Press, 1981. — MathSciNet: MR0634376.
  8. О. Н. Григорьева, О. А. Дмитриева. Моделирование линейных динамических систем большой размерности с разреженными матрицами коэффициентов / Информатика и компьютерные технологии-2011. — Донецк: Донецкий национальный технический университет, 2011. — С. 199–203.
    • O. N. Grigor'eva, O. A. Dmitrieva. Modeling linear dynamical systems of high dimension with sparse matrices of coefficients / Informatics and computer technologies-2011. — Donetsk: Donetsk national technical University, 2011. — P. 199–203. — in Russian.
  9. О. А. Дмитриева. Оптимизация выполнения матрично-векторных операций при параллельном моделировании динамических процессов // Науковi працi ДонНТУ. Сер. Обчислювальна технiка та автоматизацiя. 2014. — № 1 (26). — С. 94–100.
    • O. A. Dmitrieva. Optimization of performance of matrix and vector operations at parallel simulation of dynamic processes // Donetsk National Technical University. 2014. — no. 1 (26). — P. 94–100. — in Russian.
  10. Зеленков Г. А.. ., Хакимова А. Б. Подход к разработке алгоритмов ньютоновских методов оптимизации, программная реализация и сравнение эффективности // Компьютерные исследования и моделирование. 2013. — Т. 5, № 3. — С. 367–377. — DOI: 10.20537/2076-7633-2013-5-3-367-377
    • G. A. Zelenkov, A. B. Hakimova. Approach to development of algorithms of Newtonian methods of unconstrained optimization, their software implementation and benchmarking // Computer Research and Modeling. 2014. — V. 5, no. 3. — P. 367–377. — in Russian.DOI: 10.20537/2076-7633-2013-5-3-367-377
  11. С. П. Кундас. Обзор численных методов расчета систем уравнений строительной механики и выбор оптимальной схемы хранения данных для задач большой размерности // Вестник полоцкого государственного университета. Сер. F. 2010. — № 6. — С. 79–83.
    • S. P. Kundas. Review of numerical method for calculating equations of structural mechanics and choice of the optimal storage solutions for systems of large dimensionality // Herald of Polotsk state University. Series F. 2010. — no. 6. — P. 79–83. — in Russian.
  12. С. А. Лебедев, И. Б. Мееров, Е. А. Козинов, Д. Р. Ахмеджанов, А. Ю. Пирова, А. В. Сысоев. Двухуровневый параллельный алгоритм выполнения численной фазы разложения Холецкого для разреженных матриц / Суперкомпьютерные дни в России: Труды международной конференции. — М: Изд-во МГУ, 2015. — С. 133–144. — (28–29 сентября 2015 г., г. Москва).
    • S. A. Lebedev, I. B. Meerov, E. A. Kozinov, D. R. Ahmedzhanov, A. Yu. Pirova, Sysoev A. V.. Duplex parallel execution algorithm for the numerical phase of the decomposition of Cholesky for sparse matrices / Proceedings of the international conference Russian Supercomputing Days 2015. — Moscow: MSU, 2015. — P. 133–144. — (28–29 September 2015). — in Russian.
  13. Г. И. Малашонок, А. И. Аветисян, Ю. Д. Валеев, М. С. Зуев. Параллельные алгоритмы компьютерной алгебры / Proceedings of the Institute for System Programming. — Vol. 8 (Issue 2, in Russian).2004. — С. 169–180.
    • G. I. Malashonok, A. I. Avetisjan, Yu. D. Valeev, M. S. Zuev. Parallel algorithms of computer algebra / Proceedings of the Institute for System Programming. — Vol. 8 (Issue 2, in Russian).2004. — P. 169–180. — in Russian.
  14. Г. И. Малашонок, А. С. Щербинин. Об одном алгоритме треугольной декомпозиции в коммутативном кольце // Вестник Тамбовского университета. Сер. Естественные и технические науки. 2015. — Т. 20, № 5. — С. 1293–1302.
    • G. I. Malashonok, A. S. Shcherbinin. About algorithm for the triangular decomposition in a commutative ring // Tambov University Reports. Ser. Natural and Technical sciences. 2015. — V. 20, no. 5. — P. 1293–1302. — in Russian.
  15. Е. С. Николаев. Разреженные матрицы. Библиотека программ. — М: МГУ, 1986.
    • E. S. Nikolaev. The sparse matrix. Library programs. — M: MSU, 1986. — in Russian.
  16. Е. С. Николаев, А. Б. Кучеров. Разреженные матрицы. Численные методы и алгоритмы. — М: МГУ, 1988.
    • E. S. Nikolaev, A. B. Kucherov. The sparse matrix. Numerical methods and algorithms. — M: MSU, 1988. — in Russian.
  17. Дж. Ортега, У. Пул. Введение в численные методы решения дифференциальных уравнений. — М: Наука, 1986.
    • Dzh. Ortega, U. Pul. Vvedenie v chislennye metody reshenija differencial'nyh uravnenij. — M: Nauka, 1986. — in Russian. — MathSciNet: MR0890108.
    • J. M. Ortega, PooleW. G. . An introduction to numerical methods for differential equations. — Jr. Pitman Publishing Inc, 1981. — MathSciNet: MR0634229. — zbMATH: Zbl 0472.65060.
  18. А. О. Отаров, Э. П. Уразымбетова, А. А. Отаров. Решение неустойчивых систем линейных алгебраических уравнений методом дифференциального спуска // Вестник Каракалпакского государственного университета им. Бердаха. — Ташкент: SAYDANA-PRINT, 2010. — № 3–4 (8–9). — С. 7–15.
    • A. O. Otarov, E. P. Urazymbetova, A. A. Otarov. The solution of unstable systems of linear algebraic equations by the method of differential descent // Bulletin of Karakalpak state University After Berdakh. — Tashkent: «SAYDANA-PRINT», 2010. — no. 3–4 (8–9). — P. 7–15. — in Russian.
  19. Б. Парлетт. Симметричная проблема собственных значений. Численные методы. — М: Мир, 1983.
    • B. Parlett. Simmetrichnaja problema sobstvennyh znachenij. Chislennye metody. — M: Mir, 1983. — in Russian. — MathSciNet: MR0702348.
    • B. N. Parlett. The symmetric eigenvalue problem. — California: University of California Berkeley, 1980. — MathSciNet: MR1490034.
  20. А. В. Перельмутер. Расчетные модели сооружений и возможность их анализа. — Киев: Сталь, 2002. — 600 с.
    • A. V. Perel'muter. Design models of structures and possibility of their analysis. — Kiev: Stal, 2002. — 600 p. — in Russian.
  21. С. Писсанецки. Технология разреженных матриц. — М: Мир, 1988. — 410 с.
    • S. Pissanecki. Tehnologija razrezhennyh matric. — M: Mir, 1988. — in Russian. — MathSciNet: MR0954834.
    • S. Pissanetzky. Sparse matrix technology. — Centro Atamico Bariloche, Bariloche, Argentina. — Academic Press Inc, 1984. — MathSciNet: MR0751237. — zbMATH: Zbl 0536.65019.
  22. А. А. Самарский, А. В. Гулин. Численные методы. — М: Наука, 1969.
    • A. A. Samarskij, A. V. Gulin. Numerical methods. — M: Nauka, 1969. — in Russian. — MathSciNet: MR0514844.
  23. А. Б. Свириденко. Априорная поправка в ньютоновских методах оптимизации // Компьютерные исследования и моделирование. 2015. — Т. 7, № 4. — С. 835–863. — DOI: 10.20537/2076-7633-2015-7-4-835-863
    • A. B. Sviridenko. The correction to Newton's methods of optimization // Computer Research and Modeling. 2015. — V. 7, no. 4. — P. 835–863. — in Russian.DOI: 10.20537/2076-7633-2015-7-4-835-863
  24. А. Б. Свириденко. Взаимосвязь и реализация квазиньютоновских и ньютоновских методов безусловной оптимизации // Компьютерные исследования и моделирование. 2016. — Т. 8, № 1. — С. 55–78. — DOI: 10.20537/2076-7633-2016-8-1-55-78
    • A. B. Sviridenko. Correlation and realization of quasi-Newton methods of absolute optimization // Computer Research and Modeling. 2016. — V. 8, no. 1. — P. 55–78. — in Russian.DOI: 10.20537/2076-7633-2016-8-1-55-78
  25. М. О. Солнцева, Б. Г. Кухаренко. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. 2013. — Т. 5, № 3 (19). — С. 75–83.
    • M. O. Solnceva, B. G. Kuharenko. Application of methods of clustering nodes in graphs with sparse matrices adjacency in tasks logistics // The works of MFTU. 2013. — V. 5, no. 3 (19). — P. 75–83. — in Russian.
  26. C. A. Соловьев. Решение разреженных систем линейных уравнений методом Гаусса c использованием техники аппроксимации матрицами малого ранга // Вычислительные методы и программирование. — М: Научно-исследовательский вычислительный центр МГУ им. М. В. Ломоносова, 2014. — Т. 15. — С. 441–460.
    • C. A. Solov'ev. Application of the low-rank approximation technique in the Gauss elimination method for sparse linear systems // Numerical methods and programming. 2014. — V. 15. — P. 441–460. — in Russian.
  27. Г. Стренг. Линейная алгебра и ее применения. — М: Мир, 1980.
    • G. Streng. Linejnaja algebra i ee primenenija. — M: Mir, 1980. — in Russian.
    • G. Strang. Linear algebra and its applications. — New York, San Francisco, London: Academic Press, 1976. — MathSciNet: MR0384823. — zbMATH: Zbl 0338.15001.
  28. Р. Тьюарсон. Разреженные матрицы. — М: Мир, 1977.
    • R. T'juarson. Razrezhennye matricy. — M: Mir, 1977. — in Russian. — MathSciNet: MR0458819.
    • R. P. Tewarson. Sparse matrices. Mathematics in science and Enginiring. — Department of Applied Mathematics and Statistics State University of New York, Stony Brook, New York. — New York and London: Academic Press, 1973. — Edited by Richard Bellman.
  29. Д. К. Фаддеев, В. Н. Фаддеева. Вычислительные методы линейной алгебры. — М.–Л: Физматгиз, 1963.
    • D. K. Faddeev, V. N. Faddeeva. Computational methods of linear algebra. — M.–L: Fizmatgiz, 1963. — in Russian. — MathSciNet: MR0161454.
  30. С. Ю. Фиалко. О методах решения большеразмерных задач строительной механики на многоядерных компьютерах // Инженерно-строительный журнал. 2013. — № 5. — С. 116–124.
    • S. Yu. Fialko. About analysis of large problems of structural mechanics on multi-core computers // Magazine of Civil Engineering. 2013. — no. 5. — P. 116–124. — in Russian. — DOI: 10.5862/MCE.40.13.
  31. С. Ю. Фиалко. Прямые методы решения систем линейных уравнений в современных МКЭ-комплексах. — М: СКАД СОФТ, Издательство Ассоциации строительных вузов (АСВ), 2009. — С. 160.
    • S. Yu. Fialko. Direct methods for solving systems of linear equations in the FE-complexes. — M: SKAD SOFT, Publisher Association building universities (DIA), 2009. — P. 160. — in Russian.
  32. Дж. Форсайт, К. Молер. Численное решение систем линейных алгебраических уравнений. — М: Мир, 1969.
    • Dzh. Forsajt, K. Moler. Chislennoe reshenie sistem linejnyh algebraicheskih uravnenij. — M: Mir, 1969. — in Russian. — MathSciNet: MR0248971.
    • G. E. Forsythe, C. B. Moler. Computer solution of linear algebraic systems. — Englewood Cliffs, N. J: Prentice-Hall, Inc, 1967. — MathSciNet: MR0219223. — zbMATH: Zbl 0154.40401.
  33. А. Б. Хакимова, Г. А. Зеленков, И. Г. Рзун. Подход к увеличению эффективности мультипликативного алгоритма симплекс-метода // Динамика неоднородных систем: Труды ИСА РАН. — М: Книжный дом «ЛИБРОКОМ», 2010. — Т. 53, № 14. — С. 245–251.
    • A. B. Khakimova, G. A. Zelenkov, I. G. Rzun. Approach to increase the efficiency of the multiplicative algorithm of the simplex method // The works of ISA Russian Academy of Sciences "Dynamics of heterogeneous systems". 2010. — V. 53, no. 14. — P. 245–251. — in Russian.
  34. А. А. Цыганков. Новые условия экстремума для гладких задач с ограничениями в форме равенств // Журнал вычислительной математики и математической физики. 2001. — Т. 41, № 10. — С. 1474–1484. — zbMATH: Zbl 1045.90081.
    • A. A. Cygankov. New extremum conditions for smooth problems with constraints in form of equalities // Computational Mathematics and Mathematical Physics. 2001. — V. 41, no. 10. — P. 1474–1484. — in Russian. — Math-Net: Mi eng/zvmmf1270. — MathSciNet: MR1882263.
  35. И. Г. Черноруцкий. Методы оптимизации: Учебное пособие. — [Электронный ресурс]. — СПб, 2012. — http://elib.spbstu.ru/dl/2357.pdf.
  36. И. Г. Черноруцкий. Методы оптимизации. Компьютерные технологии. — СПб: БХВ-Петербург, 2011. — 384 с.
    • I. G. Chernoruckij. Methods of optimization. Computer technology. — SPb: BHV-Petersburg, 2011. — 384 p. — in Russian.
  37. И. Г. Черноруцкий. Практическая оптимизация и невыпуклые задачи // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. — СПб: Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский политехнический университет Петра Великого», 2013. — № 4 (176). — С. 79–86.
    • I. G. Chernoruckij. Practical optimization and nonconvex problems // Nauchnotekhnicheskie Vedomosti SPbGPU. Informatics. Telecommunications. Management. — St. Petersburg: Federal state Autonomous educational institution of higher professional education "Saint-Petersburg Polytechnic University Peter the Great", 2013. — no. 4 (176). — P. 79–86. — in Russian.
  38. О. Эстербю, З. Златев. Прямые методы для разреженных матриц. — М: Мир, 1987.
    • O. Jesterbju, Z. Zlatev. Prjamye metody dlja razrezhennyh matric. — M: Mir, 1987. — in Russian. — MathSciNet: MR0896271.
    • O. Østerby, Z. Zlatev. Direct Methods for sparse matrices. — Berlin–Heidelberg–New York–Tokyo: Spriger-Verlag, 1983. — MathSciNet: MR0716136.
  39. N. S. Bakhvalov. On the Convergence of a Relaxation Method with Natural Constraints on the Elliptic Operator // USSR Comput. Math. Math. Phys. 1966. — no. 6 (5). — P. 101–135. — DOI: 10.1016/0041-5553(66)90118-2. — MathSciNet: MR0215538. — zbMATH: Zbl 0154.41002.
  40. M. Bebendorf, W. Hackbusch. Existence of H-Matrix Approximants to the Inverse FE-Matrix of Elliptic Operators with L∞-Coefficients // Numer. Math. 2003. — no. 95 (1). — P. 1–28. — DOI: 10.1007/s00211-002-0445-6. — MathSciNet: MR1993936. — zbMATH: Zbl 1033.65100.
  41. Borne S. Le, L. Grasedyck, . Domain-Decomposition Based H-LU Preconditioners // Lecture Notes in Computational Science and Engineering. — Heidelberg: Springer, 2007. — V. 55. — P. 667–674. — DOI: 10.1007/978-3-540-34469-8_83. — MathSciNet: MR2334161.
  42. S. Chandrasekaran, P. Dewilde, M. Gu, . On the Numerical Rank of the OffDiagonal Blocks of Schur Complements of Discretized Elliptic PDEs // SIAM J. Matrix Anal. Appl. 2010. — no. 31 (5). — P. 2261–2290. — DOI: 10.1137/090775932. — MathSciNet: MR2740619. — zbMATH: Zbl 1209.65032.
  43. T. A. Davis. Direct methods for sparse linear systems // Siam. 2006. — V. 2. — MathSciNet: MR2270673. — zbMATH: Zbl 1119.65021.
  44. M. M. Dehnavi, D. M. Fernández, D. Giannacopoulos. Finite-element sparse matrix vector multiplication on graphic processing units // IEEE Transactions on Magnetics. 2010. — V. 46, no. 8. — P. 2982–2985. — DOI: 10.1109/TMAG.2010.2043511.
  45. R. P. Fedorenko. A Relaxation Method for Solving Elliptic Difference Equations // USSR Comput. Math. Math. Phys. 1962. — no. 1 (4). — P. 1092–1096. — DOI: 10.1016/0041-5553(62)90031-9. — MathSciNet: MR0137314.
  46. A. George, J. W. H. Liu. Computer Solution of Large Sparse Positive Definite Systems. — Englewood Cliffs: Prentice-Hall, 1981. — MathSciNet: MR0646786. — zbMATH: Zbl 0516.65010.
  47. A. George. Nested Dissection of a Regular Finite Element Mesh // SIAM J. Numer. Anal. 1973. — no. 10 (2). — P. 345–363. — DOI: 10.1137/0710032. — MathSciNet: MR0388756. — zbMATH: Zbl 0259.65087.
  48. T. George, V. Saxena, A. Gupta, A. Singh, A. R. Choudhury. Multifrontal factorization of sparse SPD matrices on GPUs / Parallel & Distributed Processing Symposium (IPDPS). 2011. — P. 372–383.
  49. S. A. Goreinov, E. E. Tyrtyshnikov, N. L. Zamarashkin. A Theory of Pseudo-Skeleton Approximations // Linear Algebra Appl. 1997. — V. 261, no. 1–3. — P. 1–21. — DOI: 10.1016/S0024-3795(96)00301-1. — MathSciNet: MR1448862. — zbMATH: Zbl 0877.65021.
  50. W. Hackbusch. A Sparse Matrix Arithmetic Based on H-Matrices. Part I: Introduction to H-Matrices // Computing. 1999. — no. 62 (2). — P. 89–108. — DOI: 10.1007/s006070050015. — MathSciNet: MR1694265. — zbMATH: Zbl 0927.65063.
  51. A. Kalinkin, K. Arturov. Asynchronous approach to memory management in sparse multifrontal methods on multiprocessors // Applied Mathematics. 2013. — V. 4, no. 12A. — P. 33–39. — DOI: 10.4236/am.2013.412A004.
  52. G. Karypis, V. Kumar. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Version 4.0. — Minneapolis: Univ. of Minnesota, 1998.
  53. L. J. Larsen. A modified inversion procedure for product form of the inverse linear programming codes // Comm. of ACM. 1962. — V. 5. — P. 382–383. — DOI: 10.1145/368273.368283. — zbMATH: Zbl 0106.10305.
  54. L. S. Lasdon. Optimization theory for large systems. — MacMillan Co, 1970. — MathSciNet: MR0337317. — zbMATH: Zbl 0224.90038.
  55. R. Lipton, D. Rose, R. Tarjan. Generalized Nested Dissection // SIAM J. Numer. Anal. 1979. — no. 16 (2). — P. 346–358. — DOI: 10.1137/0716027. — MathSciNet: MR0526496. — zbMATH: Zbl 0435.65021.
  56. J. W. H. Liu. The multifrontal method for sparse matrix solution: Theory and practice // SIAM review. 1992. — V. 34, no. 1. — P. 82–109. — DOI: 10.1137/1034004. — MathSciNet: MR1156290. — zbMATH: Zbl 0919.65019.
  57. Y. Saad, H. Vorst. Iterative Solution of Linear Systems in the 20th Century // J. Comput. Appl. Math. 2000. — no. 123 (1). — P. 1–33. — DOI: 10.1016/S0377-0427(00)00412-X. — MathSciNet: MR1798516. — zbMATH: Zbl 0965.65051.
  58. Y. Saad. Iterative Methods for Sparse Linear Systems // SIAM. — Philadelphia, 2003. — MathSciNet: MR1990645.
  59. D. E. Smith, W. Orchard-Hays. Computational efficiency in product form LP codes / Recent Advances in Mathematical Programming. — McGraw-Hill Book Co, 1963. — P. 211–218. — R. L. Graves, Ph. Wolfe Eds. — MathSciNet: MR0157776.
  60. E. E. Tyrtyshnikov. Mosaic-Skeleton Approximations // Calcolo. 1996. — V. 33 (1). — P. 47–57. — DOI: 10.1007/BF02575706. — MathSciNet: MR1632459. — zbMATH: Zbl 0906.65048.
  61. J. Xia. A Robust Inner-Outer Hierarchically Semi-Separable Preconditioner // Numer. Linear Algebra Appl. 2012. — no. 19 (6). — P. 992–1016. — DOI: 10.1002/nla.1850. — MathSciNet: MR3001324. — zbMATH: Zbl 1289.65047.
  62. J. Xia. Efficient Structured Multifrontal Factorization for General Large Sparse Matrices // SIAM J. Sci. Comput. 2013. — V. 35 (2). — P. 832–860. — DOI: 10.1137/120867032. — MathSciNet: MR3035488.
  63. J. Xia. Robust and Efficient Multifrontal Solver for Large Discretized PDEs / High-Performance Scientific Computing. — London: Springer, 2012. — P. 199–217.
  64. G. Zoutendijk. Methods of feasible directions. — М: Elsevier Publishing Co, 1960. — MathSciNet: MR0129119. — zbMATH: Zbl 0097.35408.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"