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

[Matthew Knepley]

On Tue, Aug 4, 2015 at 12:08 PM, Cong Li <solvercorleone at gmail.com> wrote:

> 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.
>

Yes, that is what Barry is suggesting.

  Thanks,

     Matt


> 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
>>
>
>


-- 
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/20150804/f2da47be/attachment.html>