A general iterative sparse linear solver and its parallelization for interval Newton methods

Abstract

Interval Newton/Generalized Bisection methods reliably find all numerical solutions within a given domain. Both computational complexity analysis and numerical experiments have shown that solving the corresponding interval linear system generated by interval Newton's methods can be computationally expensive (especially when the nonlinear system is large).

In applications, many large-scale nonlinear systems of equations result in sparse interval jacobian matrices. In this paper, we first propose a general indexed storage scheme to store sparse interval matrices We then present an iterative interval linear solver that utilizes the proposed index storage scheme It is expected that the newly proposed general interval iterative sparse linear solver will improve the overall performance for interval Newton/Generalized bisection methods when the jacobian matrices are sparse. In section 1, we briefly review interval Newton's methods. In Section 2, we review some currently used storage schemes for sparse systems. In Section 3, we introduce a new index scheme to store general sparse matrices. In Section 4, we present both sequential and parallel algorithms to evaluate a general sparse Jacobian matrix. In Section 5, we present both sequential and parallel algorithms to solve the corresponding interval linear system by the all-row preconditioned scheme. Conclusions and future work are discussed in Section 6.

Abstract

Интервальный метод Ньютона и обобщенный метод половинного деления гарантированно находят все численные решения в заланной области. Как анализ вычислительной сложности, гак и численные зксперимемты показали, что решение соответствующей интервальной линейной системы, полученной интервальными методами Ньютона, может потребовать значительного объема вычислений (особенно если нелинейная система велика по размерам)

На практике системы нелинейных уравнений большой размерности нередко сводятся к разреженным интервальным матрицам Якоби. В настоящей работе предлагается обобщенная индексированная схема памяти для хранения разреженных интервальных матриц, а затем вводится итеративный интервальный линейный решатель, пснользуюший эту схему Ожидается, что предложенный обобшенный итеративный итеративный интервальный линейный решатель повысит обшую производительность методов Ньютона и обобщенного метода половинного деления для разреженных матриц Якоби В разделе 1 кратко описаны интервальные методы Ньютона. В разделе 2 рассматриваются некоторые используемые в настоящее время схемы памяти для разреженных систем В