2
$\begingroup$

In my numerical linear algebra class, I learned that for some matrices, it could have an element that is a very small number that is approximately 0 (and many orders of magnitude different from all the other non-zero elements), can destroy the conditioning of a matrix.

Now I am wondering how this works practically. When we formulate the linear system $$Ax=b$$

A lot of math goes into forming the operator $A$. In the case of solving PDEs, we run into a lot of round-off issues during computations, and this, will certainly affect $A$. In some of the matrices I've formed, my operator is a sparse matrix. I notice that some elements of $A$ end up being approximately 0, but not actual zero, decreasing the sparsity, and perhaps destroying the conditioning of the matrix? Theoretically, those computations should have evaluated zero, but due to roundoff, they end up non-zero.

Would it be a good approach to go through the non-zero elements of a sparse matrix and filter out all the values close to zero and set them as zero? I have thought about doing this, but I am unsure if this is the right approach. What if those numbers that I am filtering are not theoretically zero, and they are actually very small?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Many times you know a priori what are the non-zero elements. Then you can avoid filling in the zero elements. In FEM type situations this is usually known. E.g. in the case of laplace operator you know which are the non-zero entries. In some non-linear cases, you may not know this in advance. If you do your computations in double precision then I dont think it is necessary to zero out elements that turn out to be very small but not exactly zero. If there are many such elements then maybe you want to increase the sparsity by zeroing out such elements which you know should be theoretically zero. $\endgroup$
    – cfdlab
    Nov 28, 2018 at 3:55
  • $\begingroup$ How are you getting your matrix, FD, FE, FV etc. ? $\endgroup$
    – cfdlab
    Nov 28, 2018 at 3:59
  • $\begingroup$ I am using FV. I am working with linear PDEs. I would say that for every row of the matrix, about 10-20% of the non-zero elements should be theoretically zero. I do my computations in double precision, but even so, wouldn't small numbers contribute significantly to ill-conditioning? $\endgroup$
    – anonuser01
    Nov 28, 2018 at 15:33
  • 1
    $\begingroup$ A keyword here is 'sparsity pattern', and you're thinking about removing entries that are not part of the pattern, but have accumulated through round-off errors. In practice, I don't know of anyone who does this. This is because most $\epsilon$ entries will not greatly influence your condition number, but rather only those that add a near-zero singular value. $\endgroup$
    – user20857
    Nov 28, 2018 at 17:33
  • 1
    $\begingroup$ FV methods are local: the degrees of freedom on each cell only couple with those on the immediate (face) neighbors of the cell. For sufficiently large numbers of cells, 99% or more of all matrix entries must be zero because their rows and columns correspond to cells that are not neighbors. How is that not the case for you? How are you computing these entries that you even get something nonzero due to round-off? You should not be computing anything at all for these entries! $\endgroup$
    – Wolfgang Bangerth
    Nov 28, 2018 at 18:48

1 Answer 1

Reset to default
2
$\begingroup$

For sparse matrices $A$, that are a discretized version of operators in PDEs in FE, FV, or FD, you do know your sparsity pattern before you compute the actual entries. So, you usually

  1. compute matrix elements of $A$ that are not zeros according to the sparsity pattern
  2. do not do anything with your known zeros.

In your question, it seems that you want to go one step further and analyze what is computed on step 1 and preemptively zero it out according to some tolerance criteria. Effectively, you are going to mess up with your discretized operator and solve some approximate version of that when certain values are filtered. I am not aware of this technique being practically applied and I can think of several reasons:

  • the fact that some matrix element is relatively small does not necesserily imply that the condition number will be ruined. The condition number of the matrix is determined by singular values that certainly "come from matrix entries", but not in a such straigtforward manner. As @Spencer correctly pointed out in the comments, your small matrix entry should add a near-zero singular value.
  • filtering out matrix entries is not the way to go. One can try improve the solution by filtering out singular values. In short: compute SVD decomposition of $A$, truncate it by some tolerance, solve the problem. However, that is usually done for ill-posed problems (say inverse problems), and I am not aware of this approach being applied for forward solution of PDEs.
  • filtering out of matrix entries can technically be used to form a preconditioner. But it is used together with your unfiltered matrix within an iterative solution of the system of linear equations.

So, I would certainly suggest to check if those entries actually influence the condition number of the matrix (which is unlikely). And choosing a different discretization scheme (geometry/operator) might be a much more promising route.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.