Description

The code is a collection of Fortran 90 subroutines for the factorization and the solution of  systems that admit a Cholesky-like factorization (for example, quasidefinite systems).
It is based on a modification of the package of Ng and Peyton, that performs the Cholesky factorization of a positive definite matrix. The package is included in LIPSOL 0.3, downloadable from www.caam.rice.edu/~zhang/lipsol. The whole process can be subdivided in two phases.The first phase is depending only on the structure of the matrix and its aims are performing the minimum degree reordering (ORDMMD), providing the supernodal subdivision (SFINIT) and computing the symbolic factorization (SYMFCT, BFINIT) of the matrix. These subroutines belong to the package of Ng and Peyton. In the second phase, the actual factorization of the matrix is performed by means of the subroutines INPNV (also from the Ng and Peyton package) and BLKFCT. The last one is derived from the BLKFCT subroutine of Ng and Peyton, so that it can be used in combination with the other subroutines of that package, but it produces a Cholesky-like LDL^T factorization (instead of the Cholesky factorization LL^T), where L is a triangular matrix with diagonal entries equal to 1 and D is a diagonal nonsingular matrix. The modified routine BLKFCT includes the regularization process and the possibility to apply it also to nonquasidefinite  matrices. Indeed, during the factorization, if a too small pivotal element is encoutered, it is substituted by a larger value. Moreover, the sign assigned to the pivotal element depends on its position along the diagonal: it is positive if the element belongs to the positive definite block of the matrix (the first NSUP rows), it is negative otherwise. Finally, the solution of the systems Ly = b and L^Tx = D^-1y can be obtained by means of a routine that is a modified version of the subroutine BLKSLV (included in the package of Ng and Peyton).

The effectiveness of the package of Ng and Peyton, due to a suitable use of the cache memory, is maintained.

Authors:

• Silvia Bonettini
  Dept. of Mathematics, University of Modena and Reggio Emilia - ITALY
  bonettini.silvia@unimo.it 
• Valeria Ruggiero
  Dept. of Mathematics, University of Ferrara - ITALY
  v.ruggiero@unife.it

This work is supported by the Italian FIRB Project
Parallel Algorithms and Numerical Nonlinear Optimization (grant RBAU01JYPN), http://dm.unife.it/pn2o
and by the Italian M.I.U.R. Project
Numerical Methods and Mathematical Software in Applications (grant 2004012559), http://www.math.unifi.it/~brugnano/Cofin2004.

Instructions and documentation

The file BLKFCLT.F contains all the subroutines needed for the factorization of the matrix and for the solution of the system. All the matrices involved have to be stored in the Compressed Column Storage form. As an example of the subroutines usage, download the file example.f90 .

BLKFCLT.F
example.f90