Complete pivoting strategy for the $IUL$ preconditioner obtained from Backward Factored APproximate INVerse process

Document Type: Research Paper

Authors

1 Department of Applied Mathematics‎, ‎Hakim Sabzevari University‎, ‎Sabzevar‎, ‎Iran‎.

2 Institute computational Mathematics‎, ‎Technische Universitat Braunschweig‎, ‎D-38106 Braunschweig‎, ‎Germany.

Abstract

‎In this paper‎, ‎we use a complete pivoting strategy to compute the IUL preconditioner obtained as the by-product of the Backward Factored APproximate INVerse process‎. ‎This pivoting is based on the complete pivoting strategy of the Backward IJK version of Gaussian Elimination process‎. ‎There is a parameter $\alpha$ to control the complete pivoting process‎. ‎We have studied the effect of different values of $\alpha$ on the quality of the IUL preconditioner‎. ‎For the numerical experiments section‎, ‎the IUL factorization which is coupled with the complete pivoting is compared to the ILUTP and to the left-looking version of RIF which is coupled with the complete pivoting strategy‎. ‎As the preprocessing‎, ‎we have applied the maximum weighted matching coupled the Reverse Cuthill-Mckee (RCM) and multilevel nested dissection reordering.

Keywords

Main Subjects


M. Benzi and M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput. 19 (1998), no. 3, 968--994.

M. Benzi and M. Tuma, A robust incomplete factorization preconditioner for positive definite matrices, Numer. Linear Algebra Appl. 10 (2003), no. 5-6, 385--400.

M. Bollhofer, ILUPACK software package, http://www.icm.tu-bs.de/_bolle/ilupack. Accessed 2015.

T. Davis, University of Florida Sparse Matrix Collection, http://www.cise.ufl.edu/research/sparse/matrices. Accessed 2015.

E.D. Dolan and J.J. More, Benchmarking optimization software with performance profile, Math. Program. Ser. A 91 (2002) 201--213.

I.S. Duff and J. Koster, The design and use of algorithms for permuting large entries tothe diagonal of sparse matrices, SIAM J. Matrix Anal. Appl. 20 (1999), no. 4, 889--901.

F.R. Fazel, Computing the IUL factorization coupled by the complete pivoting as the by-product of BFAPINV process, M.Sc. Dissertation, Department of Mathematics and Computer Sciences, Hakim Sabzevari University, in Persian, 2015.

J.A. George and J.W.H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981.

T. Huckle, Personal communications , 2016.

G. Karypis and V. Kumar, METIS, a Software Package for Partitioning Unstructured Graphs and Computing Fill-Reduced Orderings of Sparse Matrices, http://glaros.dtc.umn.edu/gkhome/views/metis. Accessed 2015.

J.G. Luo, A new class of decomposition for inverting asymmetric and indefinite matrices, Comput. Math. Appl. 25, no. 4, (1993) 95--104.

A. Raei, A complete pivoting strategy for the right-looking Robust Incomplete Factorization preconditioner, Comput. Math. Appl. 64 (2012), no. 8, 2682--2694.

A. Raei, ILU and IUL factorizations obtained from Forward and Backward Factored APproximate Inverse algorithms, Bull. Iranian Math. Soc. 40 (2014), no. 5, 1327--1346.

A. Raei, Left-looking version of AINV preconditioner with complete pivoting strategy, Linear Algebra Appl. 445 (2014) 103--126.

A. Raei and M. Bollhofer, Extension of inverse-based dropping techniques for ILU preconditioners, http://www.digibib.tu-bs.de/?docid=00035624.

A. Raei, B. Tolue and M. Bollhofer, Complete pivoting strategy for the left-looking Robust Incomplete Factorization preconditioner, Comput. Math. Appl. 67 (2014), no. 11, 2055--2070.

Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing, New York, 1996.

Y. Saad, Sparskit and sparse examples, http://www-users.cs.umn.edu/_saad/software. Accessed 2015.

D.K. Salkuyeh, A. Raei and H. Roohani, ILU preconditioning based on the FAPINV algorithm, Opuscula Math. 35 (2015), no. 2, 235--250.

D.K. Salkuyeh and H. Roohani, On the relation between the AINV and the FAPINV algorithms, Int. J. Math. Math. Sci. 2009 (2009), Article ID 179481, 6 pages.

J. Zhang, A procedure for computing factored approximate inverse, M.Sc. Dissertation, Department of Computer Science, University of Kentucky, 1999.

J. Zhang, A sparse approximate inverse preconditioner for parallel preconditioning of general sparse matrices, Appl. Math. Comput. 130 (2002), no. 1, 63--85.

The HSL Mathematical Software Library, http://www.hsl.rl.ac.uk. Accessed 2015.


Volume 43, Issue 5
September and October 2017
Pages 1417-1456
  • Receive Date: 02 January 2016
  • Revise Date: 26 May 2016
  • Accept Date: 01 July 2016