Improving approximate inverses based on Frobenius norm minimization

Improving approximate inverses based on Frobenius norm minimization✩ Luis Gonz´alez∗, Antonio Su´arez Department of Mathematics, University of Las Palmas de Gran Canaria, 35017 Las Palmas de Gran Canaria, Spain Abstract Approximate inverses, based on Frobenius norm minimization, of real nonsingular matrices are analyzed from a purely theoretical point of view. In this context, this paper provides several sufficient conditions, that assure us the possibility of improving (in the sense of the Frobenius norm) some given approximate inverses. Moreover, the optimal approximate inverses of matrix A∈Rn×n, among all matrices belonging to certain subspaces of Rn×n, are obtained. Particularly, a natural generalization of the classical normal equations of the system Ax =bis given, when searching for approximate inverses N6=ATsuch that AN is symmetric and kAN −IkF<AAT−IF. Keywords: Approximate inverses; Frobenius norm minimization; Trace; Spectrum; Singular values; Normal equations 1. Introduction Let Rn×nbe the set of all n×nreal matrices. In the following, A∈Rn×n is assumed to be nonsingular, the symbols AT,A−1and tr (A) stand for the transpose, the inverse, and the trace of matrix A, respectively, and Idenotes the n×nidentity matrix. Roughly speaking, by a left (right, respectively) approximate inverse of A, we mean a matrix N∈Rn×nsuch that the matrix product NA (AN, respectively) is “close to the identity” in a certain sense. This closeness may ✩Short running title: Improving approximate inverses ∗Corresponding author. Email address: [email protected] (Luis Gonz´alez) Preprint submitted to Applied Mathematics and Computation March 13, 2013 *Manuscript Click here to download Manuscript: AMCD1100877R2.tex Click here to view linked References be measured by using an adequate matrix norm, and throughout this paper we use the Frobenius norm k·kF. Moreover, we address only the case of the right approximate inverses and, for simplicity, they will be referred to as approximate inverses (but analogous results can be obtained for the left ones). More precisely, we begin with the following definition. Definition 1.1. Let A, N, N′∈Rn×n. Assume that Ais nonsingular. Then we say that Nis better approximate inverse of Athan N′, or that Nimproves N′as approximate inverse of Aif and only if kAN −IkF<kAN′−IkF. In this context, given a linear subspace Sof Rn×n, we consider the problem of obtaining the optimal approximate inverse Nof matrix Ain the subspace S. In accordance with Definition 1.1, throughout this paper the terms “the optimal” or “the best”, mean that matrix N∈Sminimizes the Frobenius norm on the residual matrix AM −I. More precisely, “the optimal” approximate inverse Nof Ain Sis the solution to the minimization problem min M∈SkAM −IkF=kAN −IkF,(1.1) but the approximate inverse Nis not necessarily optimal in any other sense of the word. The optimization problem (1.1) is tightly connected to the numerical analysis of linear systems Ax =b, A ∈Rn×n, x, b ∈Rn,(1.2) where Ais a large, sparse and nonsingular matrix. Indeed, in numerical linear algebra, the resolution of these systems is usually performed by iterative methods based on Krylov subspaces [1, 2]. In general, the convergence of such Krylov methods is not assured or may be too slow. To improve their behavior, a preconditioning matrix Nis used to transform the system (1.2) into the following equivalent system, ANy =b, x =Ny, (1.3) the so-called right preconditioned system, which is performed in order to get a preconditioned matrix AN, as close as possible to the identity [3], and N is called a (right) approximate inverse preconditioner of system (1.2). 2 Often, the preconditioners are parametrized by prescribed sparsity patterns [4, 5], but we consider here a more general case of linear parametrization where the approximate inverse N, defined by Eq. (1.1), belongs to an arbitrary matrix subspace Sof Rn×n. In [6], the authors introduce the idea to use Frobenius norm minimization for preconditioning problems. Some of the methods for constructing sparse approximate inverse preconditioners that are best approximations in the Frobenius norm, can be found, for instance, in [7, 8, 9, 10, 11, 12, 13, 14, 15] and in the references therein. It is important to highlight here that the purpose of this paper is to provide purely theoretical results about the optimal approximate inverses N∈S⊆Rn×ngiven by Eq. (1.1), in the theoretical context of Definition 1.1. However, our purpose is not to propose new algorithms for the numerical problem of preconditioning linear systems. Only, in a few cases, our results are related to computational strategies using special approximate inverse preconditioners based on Frobenius minimization. The main goal of this paper is to apply several spectral properties of the matrix product AN (Nbeing the solution to problem (1.1)) to obtain sufficient conditions for the existence of approximate inverses improving (in the sense of Definition 1.1) some given approximate inverses. By the way, we obtain the optimal approximate inverses of matrix A, among all the matrices belonging to certain linear subspaces of Rn×n. For this purpose, in Section 2, we recall some useful expressions for matrix N, and several spectral properties of matrix AN. Next, Section 3 is devoted to establish our new results: the above mentioned sufficient conditions for improving approximate inverses, as well as the optimal approximate inverses of matrix Ain certain matrix subspaces of Rn×n. Finally, conclusions are presented in Section 4. 2. Some preliminaries Now, we present some preliminary results required to make this paper self-contained. For more details about these previous results and for their proofs, we refer the reader to [16, 17, 18]. 2.1. Expressions for matrix N Taking advantage of the well-known fact that the matrix Frobenius norm derives from an inner product, the solution Nto problem (1.1) can be directly 3 obtained via orthogonal projections. Here, and in the following, orthogonality is with respect to the Frobenius inner product h·,·iF. More precisely, using the orthogonal projection theorem, the matrix product AN is the orthogonal projection of the identity onto the subspace AS, as stated by the following Lemma [16]. Lemma 2.1. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Then, the solution to problem (1.1) is characterized by tr AtANMt=tr (AM),∀M∈S, (2.1) and the minimum Frobenius norm is kAN −Ik2 F=n−tr(AN). Moreover, kANk2 F=tr(AN). Equation (2.1) implicitly gives the solution Nto problem (1.1). For the purposes of this paper, it suffices to recall here the following simple explicit formula. The basic idea simply consists of expressing the orthogonal projection AN of the identity matrix onto the subspace AS by its expansion with respect to an orthonormal basis of AS [16]. Lemma 2.2. Let A∈Rn×nbe nonsingular. Let Sbe a linear subspace of Rn×nof dimension d, and {M1, ..., Md}a basis of Ssuch that {AM1, ..., AMd} is an orthogonal basis of AS. Then, the solution to problem (1.1) is N= d X i=1 tr (AMi) kAMik2 F Mi,(2.2) and the minimum Frobenius norm is kAN −Ik2 F=n− d X i=1 [tr (AMi)]2 kAMik2 F .(2.3) Remark 2.1. In addition to formula (2.2), other explicit expressions for the optimal preconditioners Ncan be given using an arbitrary basis of subspace S. The idea consists of using the Gram-Schmidt orthonormalization procedure to obtain an orthonormal basis of AS, and then to apply Eq. (2.2). Such expressions have been developed for computational purposes in [16], and they have been applied to the preconditioning of large linear systems arising from real-world cases. 4 2.2. Spectral properties of matrix AN Let us denote by {λi(AN)}n i=1 and {σi(AN)}n i=1 the sets of eigenvalues and singular values, respectively, of the matrix product AN arranged, as usual, in nonincreasing order of their modules, i.e., |λ1(AN)| ≥ |λ2(AN)| ≥ · · · ≥ |λn(AN)| ≥ 0, σ1(AN)≥σ2(AN)≥ · · · ≥ σn(AN)≥0. The following proposition states some spectral properties of matrix AN. We refer the reader to [17, 18] for different proofs of these properties. Proposition 2.1. Let A∈Rn×nbe nonsingular and let Sbe a linear subspace of Rn×n. Then kANk2 F≤n, (2.4) 0≤tr (AN)≤n, (2.5) σn(AN)≤ |λn(AN)| ≤ 1 (2.6) and (1 − |λn(AN)|)2≤(1 −σn(AN))2≤ kAN −Ik2 F ≤n1− |λn(AN)|2≤n1−σ2 n(AN). Moreover, kAN −IkFdecreases to 0at the same time as the trace of AN increases to n, and also, at the same time as the smallest singular value σn(AN) (or the smallest eigenvalue’s modulus |λn(AN)|)of matrix AN increases to 1. 3. Improving approximate inverses of matrix A To avoid confusion, from now on |λn(A)|and |λn(AN)|denote the smallest eigenvalue’s modulus of matrices Aand AN, respectively. Similarly, σn(A) and σn(AN) stand for the smallest singular value of matrices Aand AN, respectively. Now, using Eqs. (2.4), (2.5) and (2.6), we prove the following corollaries of Proposition 2.1, which provide different sufficient conditions for improving some given approximate inverses, i.e., for reducing the Frobenius norm on the residual matrix AM −I. It is important to recall here that the sentences “is better approximate inverse of Athan...” or “the best or the optimal approximate inverse of 5 Aamong...”, used throughout this paper, have always the precise meaning stated by Definition 1.1 (and not any other meaning). The first corollary provides us the best approximate inverse of matrix A, among all the n×nscalar matrices. Corollary 3.1. Let A∈Rn×nbe nonsingular. (i)If tr (A)/∈[0, n]or if |λn(A)|>1, then there exists a scalar matrix αI which is better approximate inverse of Athan the identity matrix, i.e., ∃α∈R, α 6= 1 s.t. kA(αI)−IkF=kαA −IkF<kA−IkF. (ii)The scalar αthat minimizes kαA −IkFis α=tr (A) kAk2 F .(3.1) Proof. To prove (i) consider the matrix subspace S=span {I}of Rn×n. Suppose that N=Iis the solution to problem (1.1) for subspace S. Then, on one hand, using Eq. (2.5), we have N=I⇒tr (AN) = tr (A)∈[0, n], which contradicts the hypothesis on tr (A). On the other hand, using Eq. (2.6), we have N=I⇒ |λn(AN)|=|λn(A)| ≤ 1, which contradicts the hypothesis on λn(A). To prove (ii), just consider that the solution Nto problem (1.1) for the subspace S=span {I}can be obtained from Eq. (2.2), using the basis {I} of S. That is, N=tr (A) kAk2 F I⇒α=tr (A) kAk2 F . The following corollary provides the optimal approximate inverse of matrix A, among all scalar multiples of A. Corollary 3.2. Let A∈Rn×nbe nonsingular. (i)If tr (A2)/∈[0, n]or if |λn(A)|>1, then there exists a scalar multiple αA of Awhich is better approximate inverse of Athan Aitself, i.e., ∃α∈R, α 6= 1 s.t. kA(αA)−IkF=αA2−IF<A2−IF. 6 (ii)The scalar αthat minimizes kαA2−IkFis α=tr (A2) kA2k2 F . We omit the proof of Corollary 3.2, since it is similar to that of Corollary 3.1 if we use matrix Ainstead of I. Next corollary deals with the search of symmetric approximate inverses for symmetric matrices. Throughout this paper, the set of all n×nreal symmetric matrices is denoted by Sn(R). Corollary 3.3. Let A∈Sn(R)be nonsingular. (i)If kAk2 F> n or if |λn(A)|>1, then there exists a symmetric matrix M which is better approximate inverse of Athan Aitself, i.e., ∃M∈Sn(R),s.t. kAM −IkF<A2−IF. (ii)The symmetric matrix Nthat minimizes kAM −IkFis given by tr A2NM=tr (AM),∀M∈Sn(R). Proof. To prove (i) consider the matrix subspace S=Sn(R) of all symmetric matrices in Rn×n. Suppose that N=Ais the solution to problem (1.1) for subspace S. Then, on one hand, using Eq. (2.5), we have N=A⇒tr (AN) = tr A2=tr AAT=kAk2 F∈[0, n], which contradicts the hypothesis on kAk2 F. On the other hand, using Eq. (2.6), we have N=A⇒ |λn(AN)|=λnA2=|λn(A)|2≤1, which contradicts the hypothesis on λn(A). To prove (ii), it suffices to apply Eq. (2.1) for subspace S=Sn(R).  The following three corollaries are close related to the Frobenius norm based preconditioning of linear systems. For this reason, from now on we must assume that the solution Nto problem (1.1) is nonsingular, in order to get a nonsingular preconditioned matrix AN. First we need to set some notations. In the following, Mi,j denotes the n×nmatrix whose only nonzero term is mij = 1, eidenotes the i-th canonical vector (i.e., Aeiis the i-th column of A), and the symbols k·k2and h·,·i2stand for the Euclidean vector norm and inner product, respectively. 7 Remark 3.1. Since the only non-null column of matrix AMi,j is its j-th one, which coincides with the i-th column Aeiof matrix A, then we have tr (AMi,j) = aji,kAMi,jk2 F=kAeik2 2.(3.2) Moreover hAMi,j, AMi′,jiF=hAei, Aei′i2for all i6=i′ and hAMi,j, AMi′,j′iF= 0 for all j6=j′, so that any system of matrices {AMi,j}n j=1 is orthogonal with respect to the Frobenius inner product. Often, the diagonal matrix diag a−1 11 , a−1 22 ,...,a−1 nnis used as an approximate inverse preconditioner of system (1.2). However, this is not always the optimal choice among the diagonal approximate inverses, as the following corollary states. Corollary 3.4. Let A∈Rn×nbe nonsingular, such that aii 6= 0, for all i= 1,2,...,n. (i)If matrix Ais not diagonal, then there exists an n×ndiagonal matrix D which is better approximate inverse of Athan diag a−1 11 , a−1 22 ,...,a−1 nn, i.e., there exists D∈Rn×n(D diagonal)such that kAD −IkF<A·diag a−1 11 , a−1 22 ,...,a−1 nn −IF. (ii)The diagonal matrix Dthat minimizes kAD −IkFis D=diag a11 kAe1k2 2 ,···,ann kAenk2 2!.(3.3) Moreover, the corresponding minimum residual Frobenius norm is given by AD−I2 F=n− n X i=1 a2 ii kAeik2 2 .(3.4) Proof. To prove (i) consider the matrix subspace Sof all diagonal matrices in Rn×n. Suppose that N=diag a−1 11 , a−1 22 ,...,a−1 nnis the solution to problem (1.1) for subspace S. Then, (AN)ij =1,if i=j, aij ·a−1 jj ,if i6=j 8 and thus, we have kANk2 F= n X i=1 (AN)2 ii +X i6=j (AN)2 ij =n+X i6=jaij ·a−1 jj 2> n, since there exists i6=jsuch that aij 6= 0, because, by assumption, Ais not diagonal. But the inequality kANk2 F> n contradicts Eq. (2.4). To prove (ii), consider the canonical basis {Mi,i}n i=1 of subspace S. Since the basis {AMi,i}n i=1 of AS is orthogonal (Remark 3.1), then the solution N to problem (1.1) for the subspace Scan be obtained using Eqs. (2.2) and (3.2) D= n X i=1 tr (AMi,i) kAMi,ik2 F Mi,i = n X i=1 aii kAeik2 2 Mi,i =diag a11 kAe1k2 2 ,···,ann kAenk2 2!. Finally, to prove (3.4), it suffices to use Eqs. (2.3) and (3.2) AD−I2 F=n− n X i=1 [tr (AMi,i)]2 kAMi,ik2 F =n− n X i=1 a2 ii kAeik2 2 . Remark 3.2. The optimal diagonal (left) preconditioner b Dthat minimizes kDA −IkFwas already presented in [15], and it is given by the following expression b D=diag a11 keT 1Ak2 2 ,···,ann keT nAk2 2!. Note the similarity/duality between the above expression for b Dand Eq. (3.3) for D: The only difference between both expressions is that b Dinvolves the Euclidean norms of the rows eT iAof matrix A, while Dinvolves the Euclidean norms of its columns Aei. Anyway, our proof for Dis different from that given in [15] for b D. Obviously, the optimal diagonal approximate inverse (3.3) of matrix A, has exactly one nonzero element per column. This suggests the following question: Which is the best approximate inverse of matrix A, among all the n×nmatrices that have exactly one nonzero element per column? The answer is given in the next corollary, which generalizes Corollary 3.4. 9 [8] E. Chow, Y. Saad, Approximate inverse preconditioners via sparsesparse iterations, SIAM J. Sci. Comput. 19 (1998) 995-1023. [9] N.I.M. Gould, J.A. Scott, Sparse approximate-inverse preconditioners using norm-minimization techniques, SIAM J. Sci. Comput. 19 (1998) 605-625. [10] M. Grote, T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput. 18 (1997) 838-853. [11] T. Huckle, Approximate sparsity patterns for the inverse of a matrix and preconditioning, Appl. Numer. Math. 30 (1999) 291303. [12] T. Huckle, A. Kallischko, Frobenius norm minimization and probing for preconditioning, Int. J. Comput. Math. 84 (2007) 12251248. [13] T. Huckle, A. Kallischko, A. Roy, M. Sedlacek, T. Weinzierl, An efficient parallel implementation of the MSPAI preconditioner, Parallel Comput. 36 (2010) 273-284. [14] H.L. Ong, Fast approximate solution of large-scale sparse linear systems, J. Comput. Appl. Math. 10 (1984) 45-54. [15] P. Tarazaga, D. Cuellar, Preconditioners generated by minimizing norms, Comput. Math. Appl. 57 (2009) 1305-1312. [16] G. Montero, L. Gonz´alez, E. Fl´orez, M.D. Garc´ıa, A. Su´arez, Approximate inverse computation using Frobenius inner product, Numer. Linear Algebra Appl. 9 (2002) 239-247. [17] L. Gonz´alez, Orthogonal projections of the identity: spectral analysis and applications to approximate inverse preconditioning, SIAM Rev. 48 (2006) 66-75. [18] A. Su´arez, L. Gonz´alez, A generalization of the Moore-Penrose inverse related to matrix subspaces of Cn×m, Appl. Math. Comput. 216 (2010) 514-522. [19] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, MA, 1991. [20] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, MA, 1985. 16