The method of augmented regularized normal equations for systems with sparse matrices S.Y. Gogoleva1 1 Samara National Research University, 34 Moskovskoe Shosse, 443086, Samara, Russia Abstract A new approach for solving ill-posed problems is proposed. The approach makes it possible to effectively calculate normal pseudosolutions for ill-conditioned systems of linear algebraic equations and to find an acceptable solution with a minimum filling of sparse matrices. Keywords: regularization method; augmented system; sparse matrices; filling, pivoting 1. Introduction Many practical problems of finding solutions based on available data are typical representatives of ill-posed problems. It should be noted that such problems have a number of unpleasant properties of manipulating, and for their solution standard methods are inapplicable. Thanks to the works of academician A.N. Tikhonov developed a general strategy for constructing stable methods for solving ill-posed (unstable problems) in operator form [1]. It is based on the notion of a regularizing operator or a regularizing algorithm. Realizing this algorithm, it is necessary to solve the normal regularized systems of linear algebraic equations. This system is often ill-conditioned. It is necessary to choose the regularization parameter correctly in order to reduce the condition number. It is also important to choose a solution method that is numerically stable. Often ill-posed problems lead to systems with large and sparse coefficient matrices, in which most of the elements are zero. When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices as processing and memory are wasted on the zeroes. Sparse data is by nature more easily compressed and thus require significantly less storage. A serious problem in the storage and processing of sparse matrices is the fill-in. The fill-in of a matrix are those entries which change from an initial zero to a non-zero value during the execution of an algorithm. To reduce the memory requirements and the number of arithmetic operations used during an algorithm it is useful to minimize the fill-in. In this paper we propose an approach using a special form of augmented regularized normal equations. This approach allows solve the system of equations for substantially smaller values of the regularization parameter, as well as to reduce the error of the solution and reduce the fill-in. 2. Statement of the Problem Consider the system linear algebraic equations 𝐴π‘₯ = 𝑏, (1) where 𝐴 ∈ π‘…π‘›Γ—π‘š , 𝑏 ∈ 𝑅𝑛 . The regularized solution of the system (1) is found as π‘₯ = Argminπ‘₯βˆˆπ‘…π‘š {‖𝐴π‘₯ βˆ’ 𝑏‖22 + 𝛼 2 β€–π‘₯β€–22 }, which is equivalent to solving the regularized normal system (𝐴𝑇 𝐴 + 𝛼 2 𝐸)π‘₯ = 𝐴𝑇 𝑏, (2) 2 where 𝛼 is a regularization parameter. The condition number of the system (3) is found as 𝜎12 +𝛼 2 π‘π‘œπ‘›π‘‘2 (𝐴𝑇 𝐴 + 𝛼 2 𝐸) = 2 +𝛼 2 , πœŽπ‘š where 𝜎1 β‰₯ 𝜎1 β‰₯ β‹― β‰₯ πœŽπ‘š are the singular values of A. Since the matrix of the system is symmetric, then in the case of well conditionality, it is solved by the Cholesky method. System (2) is often ill-conditioned, then methods based on orthogonal transformations are applied, but they lead to a significant increase in the number of the arithmetic operations. Therefore, instead of system (2), we propose to consider an approach based on an augmented regularized system of equations. 3. The Method of Augmented Regularized Normal Equations with Pivoting Instead of system (3), it is proposed to consider the equivalent system of algebraic equations [2]: 𝐸 𝐴 π‘Ÿ 𝑏 ( 𝑇 )( ) = ( ) (3) 𝐴 βˆ’π›Ό 2 𝐸 π‘₯ 0 where π‘Ÿ = 𝑏 βˆ’ 𝐴π‘₯ is the residual vector. The condition number of the system matrix (3) is slightly less than the condition number of the normal system equations matrix (2). Therefore, in order to reduce the condition number, the parameter 𝛽 > 0 is introduced into the system (3): 3rd International conference β€œInformation Technology and Nanotechnology 2017” 64 Mathematical Modeling / S.Y. Gogoleva 𝛽𝐸 𝐴 π‘Ÿ 𝑏 ( 𝑇 𝛼2𝐸 ) ( 𝛽 ) = ( ) ↔ Π‘(𝛽) = 𝑑. (4) 𝐴 π‘₯ βˆ’ 0 𝛽 A regularized normal system is equivalent to a regularized augmented system. The minimum of the condition number of 𝜎2 the matrix (4) is attained for π›½βˆ— = √ π‘š + 𝛼 2 , where πœŽπ‘š is the minimal singular number of the matrix A. 2 𝜎 2 +𝛼 2 When choosing π›½βˆ—βˆ— = βˆšπ›Ό 2 the spectral condition number of the system matrix (4) will be √ 1 2 . Thus, this approach 𝛼 make it possible to increase the numerical stability of the problem and to reduce errors in solving of the equations system (1). The augmented system of equations modification leads to an increase in the dimension of the original problem. Using known methods to solve it leads to computational difficulties. Therefore, it is proposed to consider the modification of the direct projection method [4, 6] with the pivoting, which allows to reduce the number of arithmetic operations to obtain the augmented system of equations solution. Due to the special structure of the linear algebraic equations augmented system matrix and direct projection method vectors in the augmented system, from 𝑝 = 𝑛 + π‘š equations n are solved analytically. This means that it is possible to calculate in advance the values of the first n vectors and indicate the vectors structure in the next steps of the algorithm. For sparse systems, in order to reduce the fill-in, it is proposed to apply the Markowitz strategy in the direct projection method.[3] Let the k-th step of the direct projection method be performed. The number π‘Ÿ(𝑖, π‘˜) denotes the number of non-zero entries in the i-th row of the active submatrix Π‘π‘˜ and 𝑠(𝑗, π‘˜) is the number of non-zero elements in the j-th column of Π‘π‘˜ .The (π‘˜) Markowitz count of an entry с𝑖𝑗 is a value π‘€π‘–π‘—π‘˜ = (π‘Ÿ(𝑖, π‘˜) βˆ’ 1)(𝑠(𝑗, π‘˜) βˆ’ 1), (𝑖, 𝑗 = 1 … π‘˜). The count π‘€π‘–π‘—π‘˜ is equal to the number of elements that change the value at the transition to the next elimination step, if (π‘˜) (π‘˜) the entry с𝑖𝑗 is chosen as the pivot one, it is the upper border for the fill-in that occurs when с𝑖𝑗 is selected. Let π‘€π‘˜ = min{π‘€π‘–π‘—π‘˜ | 𝑖, 𝑗 = π‘˜ … 𝑛}. The Markowitz strategy is that at each step k, the entry with the Markowitz count π‘€π‘˜ is taken as the pivot. This does not necessarily mean that the fill-in minimum at the k-th step will be obtained; however, finding Markowitz count is much easier than calculating the value of the fill for each entry Π‘π‘˜ . To ensure numerical stability, we will choose the elements of the active submatrix for the role of the pivot, satisfying the condition (π‘˜) (π‘˜) |с𝑖𝑗 |𝑒 β‰₯ max |сπ‘₯𝑦 |, π‘˜β‰€π‘₯β‰€π‘š,π‘˜β‰€π‘¦β‰€π‘› where it is recommended to select the parameter u> 1. Table 1 lists the matrices from the Harwell-Boeing Collection with their characteristics: the size, the number of non-zero elements, and the condition number. [5] Table 1 . The tested matrices characteristics. Matrix Size Non-zeros Condition number ash958 958 Γ— 292 1916 2,1903E+6 flower_8_1 628 Γ— 513 1538 7,0295E+15 ch7-8-b1 1176 Γ— 56 2352 4,7861E+14 mk11-b1 990 Γ— 55 1980 9,8787E+7 well1033 1033 Γ— 320 4732 1,6613E+2 photogrammetry 1388 Γ— 390 11816 4.3591E+08 ash608 608 Γ— 188 1216 1,7661E+6 We give the system of equations solution (1) using the ill-conditioned matrix photogrammetry. The results of the numerical experiment are shown in Table 2. Table 2. The results for photogrammetry matrix. Method Matrix Pivoting Relative error Time, c Cholesky factorisation 𝐴𝑇 𝐴 - 2.8400E-8 20.1600 row 3.7416E-11 42.3949 Direct projection C method Markowitz strategy 3.4203E-12 50.0140 QR factorization 𝐴 - 4.6837E-12 78.6559 From Table 2 we see that the direct projection method for the augmented system with pivoting and the use of the Markowitz strategy yields exactly the same results as the QR method, but requires less execution time. 3rd International conference β€œInformation Technology and Nanotechnology 2017” 65 Mathematical Modeling / S.Y. Gogoleva 4. Conclusion A new approach to solving ill-posed problems is considered. This approach makes it possible to effectively calculate normal pseudosolutions of ill-conditioned linear equations systems and to find an acceptable solution in accuracy. Its modification for this problem, taking into account the sparseness of the augmented system, allows to significantly reduce the number of steps of the algorithm, as well as to reduce the amount of random-access memory and arithmetic operations. The Markowitz strategy in this modification allows to reduce the fill-in of a sparse matrix. This fact significantly simplifies the problem solving and reduces the time for calculation, which is a rather significant advantage. References [1] Tikhonov AN, Goncharsky AV, Stepanov VV, Yagola AG. Numerical methods for solving ill-posed problems . Moscow: Nauka, 1990; 229 p. [2] Zhdanov AI. The method of solving regularized normal equations. Journal of Computational Mathematics and Mathematical Physics 2012; 52(2): 205–208. [3] Zlatev Z, Esterby O. Direct methods for sparse matrices. M.: Mir, 1987; 120 p. [4] Zhdanov AI. A direct sequential method for solving systems of linear algebraic equations. Russian Academy of Science Report 1997; 356(4): 442– 444. [5] Harwell-BoeingCollection. MatrixMarket. URL: http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/ (5.02.2016). [6] Gogoleva SY, Zoteeva OV. Solution of the least squares problem on the basis of the augmented equations system method with a sparse matrix. Vestnik SSAU 2008; 2: 175–178. 3rd International conference β€œInformation Technology and Nanotechnology 2017” 66