4
$\begingroup$

I am using a multigrid preconditioned GMRES method for a nonsymmetric matrix. The matrix is the discretisation of the derivative of a nonlinear operator. Since multigrid is not the best for nonsymmetric problems I am preconditioning the 'symmetric part' of the matrix, where I am taking the symmetric part of matrix $A$ to be $(A + A^{\text{T}})/2$, where $A^{\text{T}}$ is the transpose of $A$.

My problem is that the 'symmetric part' of the matrix that I get is not positive definite. I was wondering if there is a way to get a symmetric positive definite part of a matrix which is just some manipulation of the original matrix, i.e.

$\tilde{A} = F(A)$

for $F$ some function of $A$

EDIT: From the comments and answers below I realise that I have not included a large part of the important information required for my question, so here is some supplementary information. I am using a standard geometric multigrid implementation with a pointwise Jacobi / Gauss-Seidel smoother. I am aware that using a smoothing operator that is tailored to the specific operator that I am dealing with will give better results, but I am assessing the effectiveness of the standard linear geometric multigrid implementation for some problems I am interested in. As such I ideally want to be applying the multigrid iteration to a symmetric positive definite matrix. I have information about the linear operator that I can use to get a matrix to precondition which is symmetric positive definite and 'close to' the matrix I am interested in inverting, which works quite well. What I am particularly interested in, though, is knowing if there is some 'black box' function which can give a symmetric positive definite matrix for the preconditioning that will be 'good' for a given matrix, without having knowledge of where the given matrix came from

$\endgroup$

migrated from cs.stackexchange.com Feb 18 '14 at 17:49

This question came from our site for students, researchers and practitioners of computer science.

  • 1
    $\begingroup$ This looks like it might be more appropriate for Computational Science. Keeran, if you agree, click the flag link below your question and ask the moderators to migrate it. $\endgroup$ – David Richerby Feb 18 '14 at 15:21
  • 1
    $\begingroup$ I think it's ontopic on either site, so I'd prefer to let the question sit here for a week or so. If it has no answer then, you can repost it. $\endgroup$ – Raphael Feb 18 '14 at 16:35
  • $\begingroup$ I am not sure about what I am going to say, but if you say that multigrid is not the best for non-symmetric systems, why not preconditioning the non-symmetric part $(A-A^T)/2$? $\endgroup$ – sebas Feb 18 '14 at 23:16
  • $\begingroup$ Where does this matrix come from? I gather you're using geometric multigrid, not algebraic multigrid? $\endgroup$ – Geoff Oxberry Feb 19 '14 at 9:56
  • $\begingroup$ @GeoffOxberry I am using geometric multigrid. The matrix is the discretisation of the linearisation of a nonlinear operator. I know that there is a symmetric positive definite (spd) part of the linear operator. Using the symmetrisation technique described above the 'symmetric' part of the matrix I get is not positive definite, though, so geometric multigrid is not as effective as in the spd case. For the example I am working with I could just discretise the spd part of the operator, but I want a general way to get a spd part of a matrix to see how effective it is for preconditioning $\endgroup$ – Keeran Brabazon Feb 19 '14 at 10:11
4
$\begingroup$

You seem to be under the misconception that multigrid only works for symmetric and positive definite matrices, and that you can apply a multigrid preconditioner if only you can replace the matrix by some SPD matrix. But that's not true. Multigrid works if the error components of your linear system live on all scales and if the matrix allows to construct a smoother that smoothes the error components on the finest levels. But this is not a result of matrix properties such as symmetricity or positive definiteness. Rather, it follows from the underlying differential operator.

Furthermore, if I understand you right, you want to apply the multigrid preconditioner to a matrix $f(A)$ and use this to precondition the solution of a linear system involving the matrix $A$. This will in general only bring any reduction in iteration counts if $f(A)$ and $A$ are in fact closely related. Just because you can find a function $f$ that maps any matrix $A$ to a symmetric and positive matrix $f(A)$ and for which you have a multigrid implementation does not mean that this is then automatically a good preconditioner for $A$.

$\endgroup$
  • $\begingroup$ I agree with all of the points made. I have found a closely related preconditioner which does work quite well, but I was wanting to know if there was a general way for getting a good preconditioner given a matrix without having to know where it came from. I wasn't too hopeful, but thought it would be interesting if there was. The reason I am concentrating on the symmetric positive definite property is that I am not considering constructing different smoothers other than the standard Jacobi / Gauss-Seidel, as the problems I am interested in are pure (nonlinear) diffusion without anisotropies $\endgroup$ – Keeran Brabazon Feb 19 '14 at 14:06
  • $\begingroup$ Thanks for the answer. I updated the question to include important information that I didn't give the first time round $\endgroup$ – Keeran Brabazon Feb 19 '14 at 14:52
  • 1
    $\begingroup$ I think the black box you are looking for doesn't exist. I can define many ways to construct an SPD matrix out of a general matrix $A$, for example $f(A)=A^TA+I$. But without defining what a "good" approximation is, that's meaningless. If you're looking for something that will make for a good preconditioner, I do not believe that it exists in general. Preconditioners need to reflect the eigenvalues of the original matrix, and you will not find any "simple" transformation that can do that. $\endgroup$ – Wolfgang Bangerth Feb 20 '14 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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