[petsc-users] I am wondering if there is a way to implement SPMM

[Cong Li]

Thanks very much for your suggestions.

Actually I am also considering using communication-avoiding matrix power
kernel (CA-MPK) to do SPMM. However, the communication pattern of CA-MPK
depends on the sparsity pattern. So the implementation could be very
complex for some of problems.The efficient implementation of CA-MPK is
actually one of problems I want to solve during my PhD course.

As to the optimisation 2 you suggested, is it the same idea as what Barry
Smith suggested?
I am sorry that I am a Rookie to PETSc, so I am not quite familiar with
PETSc implementation strategies.

Thanks

Cong Li

On Tue, Aug 4, 2015 at 8:34 PM, Matthew Knepley <knepley at gmail.com> wrote:

> On Tue, Aug 4, 2015 at 5:31 AM, Cong Li <solvercorleone at gmail.com> wrote:
>
>> Actually, I am trying to implement s-step krylov subspace method.
>> I want to extend the Krylov subspace by s dimensions by using monomial,
>> which can be defined as C={X, AX, A^2X, ... , A^sX},  in one loop. So, my
>> plan now is to firstly calculate the recurrence, which is P_n(x)=xP_n-1(x),
>> and then use the results to update the items in C. And then, in the next
>> loop of Krylov subspace method, the C will be updated again. This means I
>> need to update C in every iteration.
>> This continues till the convergence criteria is satisfied.
>>
>> I suppose A is huge sparse SPD matrix with millions of rows, and X is
>> tall-skinny dense matrix.
>>
>> Do you still think MATNEST is a good way to define C.
>>
>> Actually I am wondering if there is a way to do SPMM by using a submatrix
>> of C and also store the result in a submatrix of C.  If it is possible, I
>> think we can remove some of cost of data movement.
>> For example, C=[c_1, c_2,.., c_s], and I want to use the result of A*c_1
>> to update c_2, and then use he result of A*c_2(updated) to update c_3 and
>> so on.
>> I don't need the intermediate result separately, such as the result of
>> A*c_1, A*c_2. And I only need the final C.
>> Is there any SPMM function or strategies I can use to achievement this?
>>
>
> So there are two optimizations here:
>
>   1) Communication: You only communicate every s steps. If you are solving
> a transport dominated problem, this can make sense.
>       For elliptic problems, I think it makes no difference at all.
>
>   2) Computation: You can alleviate bandwidth pressure by acting on
> multiple vectors at once.
>
> I would first implement this naively with a collection of Vecs to check
> that 1) makes a difference for your problem.
> If it does, then I think 2) can best be accomplished by using a TAIJ
> matrix and a long Vec, where you shift the
> memory at each iterate.
>
>   Thanks,
>
>      Matt
>
>
>> Thanks
>>
>> Cong Li
>>
>>
>>
>> On Tue, Aug 4, 2015 at 6:46 PM, Patrick Sanan <patrick.sanan at gmail.com>
>> wrote:
>>
>>> On Tue, Aug 04, 2015 at 06:09:30PM +0900, Cong Li wrote:
>>> > I am sorry that I should have explained it more clearly.
>>> > Actually I want to compute a recurrence.
>>> >
>>> > Like, I want to firstly compute A*X1=B1, and then calculate A*B1=B2,
>>> > A*B2=B3 and so on.
>>> > Finally I want to combine all these results into a bigger matrix
>>> C=[B1,B2
>>> > ...]
>>> >
>>> > Is there any way to do this efficiently.
>>> With no other information about your problem, one literal solution might
>>> be to use MATNEST to define C once you have computed B1,B2,..
>>> However, this invites questions about what you plan to do with C and
>>> whether you require explicit representations of some or all of these
>>> matrices, and what problem sizes you are considering.
>>> >
>>> >
>>> >
>>> > On Tue, Aug 4, 2015 at 5:45 PM, Patrick Sanan <patrick.sanan at gmail.com
>>> >
>>> > wrote:
>>> >
>>> > > On Tue, Aug 04, 2015 at 03:42:14PM +0900, Cong Li wrote:
>>> > > > Thanks for your reply.
>>> > > >
>>> > > > I have an other question.
>>> > > > I want to do SPMM several times and combine result matrices into
>>> one
>>> > > bigger
>>> > > > matrix.
>>> > > > for example
>>> > > > I firstly calculate AX1=B1, AX2=B2 ...
>>> > > > then I want to combine B1, B2.. to get a C, where C=[B1,B2...]
>>> > > >
>>> > > > Could you please suggest a way of how to do this.
>>> > > This is just linear algebra, nothing to do with PETSc specifically.
>>> > > A * [X1, X2, ... ] = [AX1, AX2, ...]
>>> > > >
>>> > > > Thanks
>>> > > >
>>> > > > Cong Li
>>> > > >
>>> > > > On Tue, Aug 4, 2015 at 3:27 PM, Jed Brown <jed at jedbrown.org>
>>> wrote:
>>> > > >
>>> > > > > Cong Li <solvercorleone at gmail.com> writes:
>>> > > > >
>>> > > > > > Hello,
>>> > > > > >
>>> > > > > > I am a PhD student using PETsc for my research.
>>> > > > > > I am wondering if there is a way to implement SPMM (Sparse
>>> > > matrix-matrix
>>> > > > > > multiplication) by using PETSc.
>>> > > > >
>>> > > > >
>>> > > > >
>>> > >
>>> http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Mat/MatMatMult.html
>>> > > > >
>>> > >
>>>
>>
>>
>
>
> --
> What most experimenters take for granted before they begin their
> experiments is infinitely more interesting than any results to which their
> experiments lead.
> -- Norbert Wiener
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20150805/ed0cb1a9/attachment.html>