Question about the definiteness of the system matrix in Step-20

[Krishnakumar Gopalakrishnan]

I realize that this question is not exactly about the code/concepts behind deal.II library itself, but rather about a mathematical statement from step-20.

"After assembling the linear system we are faced with the task of solving it. The problem here is: the matrix has a zero block at the bottom right (there is no term in the bilinear form that couples the pressure p with the pressure test function q), and it is indefinite".

My question is about the indefiniteness of the matrix. In my understanding, a matrix is indefinite if it has both positive and negative eigen values.  However, there has not been any discussion thus far in step-20 that comment about the eigen-values. How was the statement about the indefiniteness then made?   Can someone here explain why that matrix is indefinite?

Regards,

Krishna

[David Wells]

Hi Krishna,

This is a classic linear algebra result - a symmetric matrix is
positive definite if and only if it has positive pivots. Since this
matrix has a zero block it does not even have a full set of pivots so
it cannot be positive definite.

Thanks,
David Wells

> --
> The deal.II project is located at http://www.dealii.org/
> For mailing list/forum options, see https://groups.google.com/d/forum/dealii?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "deal.II User Group" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/ec88d69a-4b26-43cb-915b-b3ae1fdfa3aa%40googlegroups.com.

[Krishnakumar Gopalakrishnan]

Dear Dr David Wells,

Thank you for the explanation. However, this only satisfies me partially because the very next statement in that tutorial says:

"We would have to resort to other iterative solvers instead, such as MinRes, SymmLQ, or GMRES, that can deal with indefinite systems. However, then the next problem immediately surfaces: due to the zero block, there are zeros on the diagonal and none of the usual, "simple" preconditioners (Jacobi, SSOR) will work as they require division by diagonal elements."

If the cause of the indefiniteness is not due to the eigen-value test, but rather due to the simple fact the pivot elements in the lower-right block is zero, then we have only ONE root cause of  all difficulties.  I am rephrasing the issues as follows (please correct me if my understanding is incorrect)

"Two difficulties arise due to the zero pivots in the bottom-right block of the matrix. 

1. Firstly, following a classical result from linear algebra, such matrices are indefinite and the conjugate gradient solver cannot be applied. We would have to resort to other iterative solvers instead, such as MinRes, SymmLQ, or GMRES, that can deal with indefinite systems.
2. Secondly, due to the zero block, there are zeros on the diagonal and none of the usual, "simple" preconditioners (Jacobi, SSOR) will work as they require division by diagonal elements"

Regards,

Krishna

> To unsubscribe from this group and stop receiving emails from it, send an email to dea...@googlegroups.com.

[David Wells]

Dear Krishna,

Allow me to clarify my previous statement. From Strang (intro to
linear algebra, 5th edition, page 352):

When a symmetric matrix S has one of these five properties, it has them all:
1. all n pivots of S are positive.
2. all n upper left determinants are positive.
3. all n eigenvalues of S are positive.
4. x^T S x is positive except at x = 0. This is the energy-based definition.
5. S equals A^T A for a matrix A with independent columns.

i.e., the statement on eigenvalue positivity and the statement on
pivots are *equivalent*, i.e., containing a zero block causes the same
difficulties as the issues with the spectra since one implies the
other.

Thanks

> To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/2e309994-0d67-4809-bb28-0c07a142184e%40googlegroups.com.

[Wolfgang Bangerth]

On 2/1/20 12:44 PM, Krishnakumar Gopalakrishnan wrote:
>
>
> "_Two difficulties_ arise due to the _*zero pivots*_ in the bottom-right block
> of the matrix.
>
> 1. Firstly, following a classical result from linear algebra, such matrices

> are indefinite and the conjugate gradient solver cannot be applied. We
> would have to resort to other iterative solvers instead, such as MinRes,
> SymmLQ, or GMRES, that can deal with indefinite systems.

> 2. Secondly, due to the//zero block, there are zeros on the diagonal and none

> of the usual, "simple" preconditioners (Jacobi, SSOR) will work as they
> require division by diagonal elements"

How about this:
https://github.com/dealii/dealii/pull/9470

Best
W.


--
------------------------------------------------------------------------
Wolfgang Bangerth email: bang...@colostate.edu
www: http://www.math.colostate.edu/~bangerth/

[David Wells]

Wolfgang pointed out to me that the pivot based answer is wrong -
fortunately I have another explanation :)

If we have the block matrix

A B^T

B 0

where A is SPD and B has linearly independent rows, this matrix has
equal eigenvalues to

I 0 A B^T A B^T
* =
-B A^-1 I B 0 0 -B A^-1 B^T

since the eigenvalues of the leftmost matrix are all 1 (its triangular
with 1s on the main diagonal). The eigenvalues of the rightmost matrix
are the eigenvalues of A and the eigenvalues of -B A^-1 B^T. Since A
is SPD, we can rewrite A^-1 = L L^T (its Cholesky factorization) so -B
A^-1 B^T = -B L L^T B^T = -(B L) (B L)^T: a second Cholesky
factorization. Hence the bottom right is negative definite and
therefore the matrix as a whole is indefinite.

Thanks,
David

> --
> The deal.II project is located at http://www.dealii.org/
> For mailing list/forum options, see https://groups.google.com/d/forum/dealii?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "deal.II User Group" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/5d8d0138-aa41-383f-963e-6cdb57fba6b8%40colostate.edu.

[Wolfgang Bangerth]

On 2/4/20 8:50 AM, David Wells wrote:
> since the eigenvalues of the leftmost matrix are all 1 (its triangular
> with 1s on the main diagonal). The eigenvalues of the rightmost matrix
> are the eigenvalues of A and the eigenvalues of -B A^-1 B^T. Since A
> is SPD, we can rewrite A^-1 = L L^T (its Cholesky factorization) so -B
> A^-1 B^T = -B L L^T B^T = -(B L) (B L)^T: a second Cholesky
> factorization. Hence the bottom right is negative definite and
> therefore the matrix as a whole is indefinite.

Yes, nice. This also explains the number of positive and negative
eigenvalues: As many positive eigenvalues as there are unknowns
represented by the A block (in the context of the mixed Laplace, as many
as there are 'u' variables), and as many negative eigenvalues as the
number of rows in the bottom left block (as many as there are 'p'
variables).