# Different Versions of ILU and IUL Factorizations Obtained from Forward and Backward Factored Approximate Inverse Processes—Part I

Authors: Amin Rafiei; Fatemeh Shahlaei
Journal: Advances in Numerical Analysis
 (2011)

---

## Abstract

We present an incomplete UL (IUL) decomposition of matrixA which is extracted as a by-product of BFAPINV (backward factored approximate inverse) process. We term this IUL factorization as IULBF. We have used ILUFF [3] and IULBF as left preconditioner for linear systems. Different versions of ILUFF and IULBF preconditioners are computed by  using  different dropping techniques. In this paper, we compare quality of different versions of ILUFF and IULBF preconditioners.


---

## Body

## 1. Introduction

Consider the linear system of equations(1.1)AX=b,
where the coefficient matrix A∈Rn×n is nonsymmetric, nonsingular, large, sparse, and X,b∈Rn. Suppose M≈A. Linear system (1.2)M-1AX=M-1b,
is termed left preconditioned system of system (1.1) and matrix M is called left preconditioner matrix [1]. System (1.2) is solved by Krylov subspace methods [1].Suppose that matrixA is nonsymmetric. Also, suppose that W=[w1T,…,wnT]T and Z=[z1,…,zn] are unit lower and upper triangular matrices, respectively, and D=diag(d1,…,dn) is a diagonal matrix. FFAPINV (forward factored approximate inverse) Algorithm [2], computes matrices W, Z, and D such that relation (1.3)WAZ≈D,
holds. It is possible to obtain an incomplete LU (ILU) decomposition of matrix A, as a by-product of FFAPINV process, such that L is an unit lower triangular and U is an upper triangular matrix and (1.4)A≈M=LU.
Matrix M in (1.4) is called ILUFF preconditioner (ILU factorization obtained from forward factored approximate inverse process) [3]. The approximate inverse factors W, Z and D in (1.3) and L, U matrices in (1.4) satisfy the two following relations: (1.5)L≈W-1,U≈DZ-1.In Algorithms1 and 2, A:,j and Aj,: refer to jth column and jth row of matrix A, respectively.Algorithm 1: ILUFF algorithm.
(1)w1=e1T,z1=e1,d1=a11.(2)forj=2 to n  do(3)wj=ejT,zj=ej.(4)for  i=1 to j-1do(5)Lji=Aj,:zidi,Uij=wiA:,jdi(6)    apply a dropping rule toLji and to Uij(7)zj=zj-(wiA:,jdi)zi,  wj=wj-(Aj,:zidi)wi(8)    for alll≤i apply a dropping rule to zlj and to wjl(first format of dropping forW and Z)(9)end for(10) for alll≤j apply a dropping rule to zlj and to wjl(second format of dropping forW and Z)(11)dj=wjA:,j (if A is not positive definite)(12)dj=wjAwjT (if A is positive definite)(13)end for(14)  ReturnL=(Lij) and U=(diUij)Algorithm 2:IULBF algorithm.
(1)wn=enT,zn=en,dn=ann.(2)for  j=n-1 to 1 do(3)wj=ejT,zj=ej.(4)fori=j+1 to n  do(5)Uji=Aj,:zidi,Lij=wiA:,jdi(6)    apply a dropping rule toUji and to Lij(7)zj=zj-(wiA:,jdi)zi,wj=wj-(Aj,:zidi)wi(8)    for alll≥i apply a dropping rule to zlj and to wjl(first format of dropping forW and Z)(9)end for(10) for alll≥j apply a dropping rule to zlj and to wjl(second format of dropping forW and Z)(11)dj=wjA:,j (if A is not positive definite)(12)dj=wjAwjT (if A is positive definite)(13)end for(14)  ReturnL=(djLij) and U=(Uij)In Section2 of this paper, we present different dropping strategies for W, Z and L, U factors of ILUFF preconditioner. In Section 3, we first introduce the IULBF preconditioner and then, we present different dropping strategies for this preconditioner. In Section 4, we present numerical results.


## 2. Different Versions of ILUFF Preconditioner

Algorithm1,which has been presented in the next page, computes the ILUFF preconditioner.Suppose thatεZ and εW are the drop tolerance parameters for Z and W matrices, respectively. We have used two strategies to drop entries of zj and wj vectors in ILUFF algorithm.(i) First Dropping Strategy
In this strategy, only line 8 of Algorithm1 will be run and line 10 will not. In this case, entries zlj and wjl, for l≤i<j are dropped when
(2.1)|zlj|≤εZ,|wjl|≤εW.(ii) Second Dropping Strategy
In this strategy, only line 10 of Algorithm1 will be run and line 8 will not. In this case, the whole vectors zj and wj are computed as
(2.2)zj=ej-∑i=1j-1(wiA:,jdi)zi,wj=ejT-∑i=1j-1(Aj,:zidi)wi,
and then, entries wjl and zlj, for l≤j, are dropped when criterions (2.1) are satisfied.We have used two strategies to drop entries ofL and U matrices in ILUFF algorithm.(i) Inverse-Based Dropping Strategy
LetεL,W be the same drop tolerance parameter for L and W matrices and εU,Z be the same drop tolerance parameter for U and Z matrices. Consider εL,W as εW and εU,Z as εZ. We drop entries zlj and wjl, for l≤i<j, when criterions (2.1) hold. Then, in line 6 of Algorithm 1, entries Lji and Uij, for i<j, are dropped when
(2.3)|Lji|‖Wi,:‖1≤εL,W,|Uij|‖Z:,i‖∞≤εU,Z.(ii) Simple Dropping Strategy
LetεL and εU be the drop tolerance parameters for L and U matrices. In line 6 of Algorithm 1, entries Lji and Uij, for i<j, are dropped when
(2.4)|Lji|≤εL,|Uij|≤εU.
Different versions of ILUFF preconditioners are computed by using different dropping strategies in Algorithm 1.(i) ILUFF1
In Algorithm1, first dropping strategy is used to drop entries of W and Z matrices and simple dropping strategy is used to drop entries of L and U matrices.(ii) ILUFF2
In Algorithm1, first dropping strategy is used to drop entries of W and Z matrices and inverse-based dropping strategy is used to drop entries of L and U matrices.(iii) ILUFF3
In Algorithm1, second dropping strategy is used to drop entries of W and Z matrices and simple dropping strategy is used to drop entries of L and U matrices.(iv) ILUFF4
In Algorithm1, second dropping strategy is used to drop entries of W and Z matrices and inverse-based dropping strategy is used to drop entries of L and U matrices.


## 3. IULBF Preconditioner and Its Different Versions

Suppose thatW=[w1T,…,wnT]T and Z=[z1,…,zn] are unit upper and lower triangular matrices, respectively, and D=diag(d1,…,dn) is a diagonal matrix. BFAPINV algorithm [2, 4] computes matrices W, Z, and D such that relation (1.3) holds. We obtain an IUL decomposition of matrix A, as a by-product of BFAPINV process, such that L is a lower triangular and U is an unit upper triangular matrix and (3.1)A≈M=UL.MatrixM in relation (3.1) is called IULBF preconditioner (IUL factorization obtained from backward factored approximate inverse process). Algorithm 2 computes the IULBF preconditioner. The approximate inverse factors W, Z, and D in (1.3) and L, U matrices in (3.1) satisfy the two following relations: (3.2)U≈W-1,L≈DZ-1.Suppose thatεZ and εW are the drop tolerance parameters for Z and W matrices, respectively. We have used two strategies to drop entries of zj and wj vectors in IULBF algorithm.(i) First Dropping Strategy
In this strategy, only line 8 of Algorithm2 will be run and line 10 will not. In this case, entries zlj and wjl, for j<i≤l are dropped when criterions
(3.3)|zlj|≤εZ,|wjl|≤εW,
hold.(ii) Second Dropping Strategy
In this strategy, only line 10 of Algorithm2 will be run and line 8 will not. In this case, the whole vectors zj and wj are computed as
(3.4)zj=ej-∑i=j+1n(wiA:,jdi)zi,wj=ejT-∑i=j+1n(Aj,:zidi)wi,
and then, entries wjl and zlj, for l≥j, are dropped when criterions (3.3) are satisfied.We have used two strategies to drop entries ofL and U matrices in IULBF algorithm.(i) Inverse-Based Dropping Strategy
LetεU,W be the same drop tolerance parameter for U and W matrices and εL,Z be the same drop tolerance parameter for L and Z matrices. Consider εU,W as εW and εL,Z as εZ. We drop entries zlj and wjl, for j<i≤l, when criterions (3.3) hold. Then, in line 6 of Algorithm 2, entries Lij and Uji, for i>j, are dropped when(3.5)|Lij|‖Z:,i‖∞≤εL,Z,|Uji|‖Wi,:‖1≤εU,W.(ii) Simple Dropping Strategy
LetεL and εU be the drop tolerance parameters for L and U matrices. In line 6 of Algorithm 2, entries Lij and Uji, for i>j, are dropped when
(3.6)|Lij|≤εL,|Uji|≤εU.
Different versions of IULBF preconditioner are computed by using different dropping strategies in Algorithm 2.(i) IULBF1
In Algorithm2, first dropping strategy is used to drop entries of W and Z matrices and simple dropping strategy is used to drop entries of L and U matrices.(ii) IULBF2
In Algorithm2, first dropping strategy is used to drop entries of W and Z matrices and inverse-based dropping strategy is used to drop entries of L and U matrices.(iii) IULBF3
In Algorithm2, second dropping strategy is used to drop entries of W and Z matrices and simple dropping strategy is used to drop entries of L and U matrices.(iv) IULBF4
In Algorithm2, second dropping strategy is used to drop entries of W and Z matrices and inverse-based dropping strategy is used to drop entries of L and U matrices.


## 4. Numerical Results

In this section, we report results of left preconditioned GMRES(16) method [1]. Preconditioners are ILUFF1, ILUFF2, ILUFF3, ILUFF4, IULBF1, IULBF2, IULBF3, and IULBF4. All coefficient matrices are nonsymmetric and from University of Florida Sparse Matrix Collection [5]. Vector b is Ae in which e=[1,…,1]T. We have written codes of ILUFF1, ILUFF2, ILUFF3, ILUFF4, IULBF1, IULBF2, IULBF3, IULBF4, and GMRES(16) in MATLAB, and we have run all the experiments on a machine with 1GB of RAM memory. In all the experiments, if the pivot element dj (lines 11 and 12 of ILUFF and IULBF algorithms) is less than the machine precision, then we replace it by 10-4. Density of preconditioners is defined as (4.1)density=nnz(L)+nnz(U)nnz(A),in whichnnz(L), nnz(U), and nnz(A) refer to the number of nonzero entries of L,U, and A matrices, respectively. In all the experiments, we have selected εL,εU, εW, εZ, εL,Z, εU,W, εL,W, and εU,Z equal to 0.1.Table1, reports results of GMRES(16) method without preconditioning. In this table, n indicates the dimension of the matrix and PD column indicates whether or not the matrix is positive definite. Yes (no) in this column means that the matrix is (is not) positive definite. Itime, indicates the iteration time of GMRES(16) without preconditioning and it, is the number of iterations of GMRES(16) method. Itime is in seconds. In this table, + means that there is no convergence after 10,000 iterations. In all the experiments, the stopping criterion is (4.2)‖rk‖2‖r0‖2≤10-8,Table 1
Information of GMRES(16) method without preconditioning and matrix properties.
MatrixnnnzPDItimeithor-1314344182No67.5944273sherman2108023094No++cavity05118232632No0.87527cavity06118229675No++sherman411043786No0.53123epb017947764No++pde2961296114585yes0.73418in whichrk is the kth residual vector of the system and r0 is the initial residual vector. In all the experiments, the initial guess is the zero vector.In Table2, the information of ILUFF1, ILUFF2, ILUFF3, and ILUFF4 preconditioners are presented and also in Table 3, the information of IULBF1, IULBF2, IULBF3, and IULBF4 preconditioners are presented. In Tables 2 and 3, Ptime is the preconditioning time and density is the density of preconditioner. Ptime is also in seconds.Table 2
properties of ILUFF1, ILUFF2, ILUFF3, and ILUFF4 preconditioners.
MethodILUFF1ILUFF2ILUFF3ILUFF4DensityPtimeDensityPtimeDensityPtimeDensityPtimehor-1310.98469622.0311.09899643.860.99043532.4221.07556232.64sherman20.463237466.5310.682342742.4320.462847637.2030.687668666.312cavity050.272646736.3430.3389921567.2230.2805531079.630.3680131139.59cavity060.291794678.7820.3762431484.220.2956369930.407515817.828sherman41.243001266.2031.312467804.9221.243001319.1721.321447574.328epb01.575348943.0931.9819682360.441.7503861274.882.2485831777.27pde29611.2347636996.831.327048108631.2482695879.31.3342489262.47Table 3
Properties of IULBF1, IULBF2, IULBF3, and IULBF4 preconditioners.
MethodIULBF1IULBF2IULBF3IULBF4DensityPtimeDensityPtimeDensityPtimeDensityPtimehor-1310.89335234.4221.10401762.111.04662826.2191.88952763.328sherman21.434745766.1872.8340691166.110.823720562.0941.3354981263.34cavity050.6820301596.861.4783041887.420.686106803.251.5380002071.98cavity060.651693663.9531.5499581870.220.657894791.4221.6287451337.67sherman41.270470789.6871.345483870.6721.386952459.6252.055203622.031epb00.8507211077.480.8539413577.971.009274951.6881.3567752924.58pde29611.2786427344.641.35701115909.71.3094274634.162.1808719440.33In Table4, results of left preconditioned systems by using different versions of ILUFF preconditioner have been presented, and also in Table 5 results of left preconditioned systems by using different versions of IULBF preconditioner have been presented. In Tables 4 and 5, Ttime is the total time which is the sum of preconditioning time and iteration time, and it is the number of iterations of left preconditioned GMRES(16). In these tables, + indicates that no convergence has been obtained in 5000 iterations.Table 4
Information of preconditioned GMRES(16) method by using different versions of ILUFF preconditioner.
MethodILUFF1ILUFF2ILUFF3ILUFF4itTtimeitTtimeitTtimeitTtimehor-131423.031345.4868232.922232.984sherman2++++++++cavity05++++++1912324.7cavity06++++++96926.188sherman43270.3243810.7343322.6873577.485epb012978.40582385.63131335.8981795.58pde296147027.38410894.745928.3639294.05Table 5
Information of preconditioned GMRES(16) method by using different versions of IULBF preconditioner.
MethodIULBF1IULBF2IULBF3IULBF4itTtimeitTtimeitTtimeitTtimehor-131334.969363.344226.828163.328sherman2++++++11265.38cavity0531600.6921891.523808.70312074.26cavity063668.09321872.953795.43811339.13sherman43792.6092874.1412462.0162626.094epb0241142.06233673.17221025.64223010.25pde296137376.75315940.324648.4419449.7


## 5. Conclusion

Results of Tables1 and 4 show that ILUFF1, ILUFF2, ILUFF3, and ILUFF4 preconditioners are useful tools to decrease the number of iterations of GMRES(16) method and results of Tables 1 and 5 show that IULBF1, IULBF2, IULBF3, and IULBF4 preconditioners are also useful tools to decrease the number of iterations of GMRES(16) method.Comparison of columns 2 and 6 of Table4 indicates that sometimes ILUFF3 preconditioner decreases the number of iterations of GMRES(16) method a little bit more than ILUFF1 preconditioner and some other times it is vice versa. Comparison of columns 2 and 4 and columns 6 and 8 of this table, also shows that ILUFF2 preconditioner decreases the number of iterations of GMRES(16) method more than ILUFF1 preconditioner and ILUFF4 preconditioner decreases the number of iterations of GMRES(16) method more than ILUFF3 preconditioner.Comparison of columns 2 and 6 of Table5 indicates that IULBF3 preconditioner decreases the number of iterations of GMRES(16) method a little bit more than IULBF1 preconditioner. Comparison of columns 2 and 4 and columns 6 and 8 of this table, also shows that IULBF2 preconditioner decreases the number of iterations of GMRES(16) method more than IULBF1 preconditioner and IULBF4 preconditioner decreases the number of iterations of GMRES(16) method more than IULBF3 preconditioner.Comparison of columns of Tables4 and 5 indicate that (except for matrix epb0) different versions of IULBF preconditioner decrease the number of iterations of GMRES(16) method more than different versions of ILUFF preconditioner.



---

*Source: 703435-2011-12-25.xml*