[petsc-dev] Bordered systems and low-rank corrections

[Mark F. Adams]

Woodbury does not seem natural (ie, efficient) when A is solved iteratively.  These methods rely on multiple solves with A being almost the same cost as one solve, most of the cost going into the matrix setup (factorization).  This is generally not the case with iterative solvers.  How does Woodbury work with inexact solves?  It looks to me like there are rank-of-B + 2 solves here.  Uzawa solvers (iterate on Schur compliment) seem better -- they work fine with inexact solves for A and you can precondition them easily for these special matrices with explic (D - C diag(A)^-1 B)^-1.  They converge very fast, like one digit per iteration even w/o preconditioning in my experience.

On Nov 4, 2011, at 11:23 AM, Jed Brown wrote:

> On Fri, Nov 4, 2011 at 09:13, Matthew Knepley <knepley at gmail.com> wrote:
> So that means the construction layout of C should mirror B. I wonder if that is strange.
> 
> The ownership rows of B are normally the same as the ownership rows of A. Similarly for columns of C.
>  
> Also, does D have a few rows on each proc, meaning B would be spread out too?
> 
> It doesn't matter where D (usually dense) is stored because it will typically be used redundantly. (These algorithms only make sense when D is pretty small. In practice, it is usually less than 10x10.)
>  
> We can easily implement MatSetValues_Transpose() to facilitate convenient assembly of bordered systems using MatSetValuesLocal(). Does anyone have a better idea for constructing these things?
> 
> Constructing B and C together I think might be the easiest, and having an option for C = B^T.
> 
> You construct them together, but you want C to have a column partition, otherwise some process will be overloaded.
>  
>  
> The Woodbury formula stuff can probably be a new PC that operates on a MATSCHURCOMPLEMENT by doing direct solves with the eliminated matrix (typically redundantly in this case, because the dimension should be small for this to make sense). Other API suggestions?
> 
> I think we need an example.
> 
> You just apply the formula. Setup involves solving (perhaps approximately) with a few vectors, then the convergence is rate is normally the same as for A, with a few extra vector operations per iteration.
> 
> http://en.wikipedia.org/wiki/Woodbury_matrix_identity

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111104/bd7b9d8c/attachment.html>