Next: 1.4 Solution by domain decomposition Up: 1 Solution of linear systems Prev: 1.2 Solution by a direct method Contents

1.3 Solution by an iterative method

1.3.1 Introduction

The methods presented in this chapter are classical methods, of conjugate gradient type, for the solution of linear systems. We can distinguish between:

• The classical conjugate gradient method, preconditioned   or not, used when matrix A of the linear system to be solved is symmetric positive definite  .
• The accelerated double conjugate gradient method   preconditioned by incomplete factorization   of matrix A, for the non-symmetric case .

The first method is implemented in the MODULEF code with three different preconditioning techniques. The matrix is stored in an AMAT type data structure.

1.3.2 The AMAT data structure

For more details consult [MODULEF User Guide - 2].

Contents

This DS is used to store the non-zero coefficients of a "finite element" type rectangular or square sparse matrix. This type of storage is called compact storage.

The DS AMAT is composed of seven arrays of predefined order.

Array AMA0:

General information.

This integer array contains 32 variables, giving a description of the job (title, date, name), of the DS AMAT (type, level, ...), and indicates the presence (or absence) of array AMA1:

1:20 TITLE

the job title in 20 words of 4 characters (stored in integers),

21:22 DATE

the creation date in 2 words of 4 characters (ditto),

23:28 NOMCRE

the name of the creator in 6 words of 4 characters (ditto),

29 'AMAT'

the DS type,

30 NIVEAU

the DS level,

31 ETAT

a reserved parameter,

32 NTACM

the number of supplementary arrays corresponding to the DS.
(they are described in array AMA1).

Array AMA1:

Description of any supplementary arrays.

This array is analogous to array B1 of DS B (see this DS).

Array AMA2:

General matrix description.

This integer array contains 10 values:

1 NTDL

matrix order,

2 NTYP

the type of matrix coefficients,

3 NTCOEF

the number of a priori non-zero matrix coefficients,

4 NMO56

the number of words necessary in M.M. to store arrays AMA5 and AMA6,

5 NPAGE

the number of pages for the matrix (if secondary memory is used),

6 NCODSA

the type of matrix storage:

• 1: symmetric matrix; only the lower triangle is stored, line per line,
• 0: diagonal matrix,
• -1: non-symmetric matrix; stored line per line, the diagonal coefficient coming last.
• -l: non-symmetric rectangular matrix; stored line per line, of l lines and NTDL columns,
  

7 ND

the number of degrees of freedom per node if it is constant, or 0,

8 NOE

the number of nodes,

9 NMASMS

the number of matrices assembled and stored in S.M. (if 0: AMA5 exists but AMA6 is absent),

10 NFACTO

the type of matrix factorization,

• 0: no factorization,
• 1: complete or incomplete Cholesky factorization,
• 2: complete or incomplete Crout factorization.

Array AMA3:

Pointer to the last line on each page.

This integer array of NPAGE + 1 words contains:

• AMA3(1) = 0,
• AMA3(i+1) = the number of the last line of page i of the matrix.

Array AMA4:

Pointer to the diagonal coefficient of each line.

This integer array of NTDL + 1 (or 2) words in length contains:

• if NCODSA = 0
  • AMA4(1) = 0
  • AMA4(2) = NTDL. In this case, array AMA5 does not exist.
• if NCODSA = 1 or -1
  • AMA4(1) = 0
  • AMA4(i+1) = the index of the couple (i,A of the diagonal coefficient A (points therefore to AMA5 and AMA6)
• if NCODSA = -l
  • AMA4(1) = 0
  • AMA4(i+1) = the number of the last coefficient of line i.

Array AMA5:

Pointer to the columns.

This integer array contains NTCOEF words if NCODSA 0 and 0 words if not:

• AMA5(k) = column number of the k-th a priori non-zero matrix coefficient .

Array AMA6:

The matrix coefficients.

This array of type NTYP contains the NTCOEF non-zero matrix coefficients:

• AMA6(k) = value of the k-th non-zero matrix coefficient.

Example 1: Diagonal matrix in M.M.

Consider the 9-th order matrix shown below (the values indicated correspond to the rows of the matrix storage and not matrix coefficients):

Thus, we have:

• NCODSA = 0
• array AMA3: (0 9)
• array AMA4: (0 9)
• array AMA5 does not exist
• array AMA6:
  

Example 2: Symmetric matrix in M.M.

Consider the following 9-th order matrix (the values indicated correspond to the rows of the matrix storage and not to the matrix coefficients):

Thus, we have:

• NCODSA = 1
• array AMA3:
  

• array AMA4:
  

• array AMA5:
  

• array AMA6:
  
  

The correspondence between arrays AMA3, AMA4 and AMA5, therefore the position of the matrix coefficients in array AMA6, is illustrated in figure 1.1.

 
Figure 1.1: Correspondence for example 2 

Example 3: Non-symmetric matrix in M.M.

Consider the following 9-th order matrix (the values indicated correspond to the rows of the matrix storage and not to the matrix coefficients):

Thus, we have:

• NCODSA = -1
• array AMA3:
  

• array AMA4:
  

• array AMA5:
  

• array AMA6:
  
  

The correspondence between arrays AMA3, AMA4 and AMA5, therefore the positions of the matrix coefficients in array AMA6, is illustrated in figure 1.2.

 
Figure 1.2: Correspondence for example 3 

For the symmetric case , matrix A is stored in a one-dimensional array AMAT6  as follows: for each row i, we only retain the non-zero coefficients , for ( see the description of D.S. MUA for the definition of mc(i)), ordered according to increasing index of column j. The rows are therefore ordered in increasing order in AMAT6. To manage the correspondence between AMAT6 and A, pointer AMAT4  is used to indicate the address of the last non-zero coefficient in AMAT6 for each row i. Lastly, pointer AMAT5  of the same size as AMAT6, and ordered in a coherent manner, gives the corresponding index of column j for each coefficient . We therefore only store the non-zero coefficients of matrix A. Address ia in AMAT6 of an arbitrary coefficient is not accessible directly, and it is necessary to search for the column j's index in AMAT5 between addresses AMAT4(i)+1 and AMAT4(i+1).

For the non-symmetric case , we adopt the same form of storage, i.e. we keep all the non-zero coefficients of the complete row, by ordering them by increasing column index, with the exception of the diagonal coefficient, placed at the end of the row.

This storage mode is called compact storage , also called Morse storage  in MODULEF.