[Trilinos-Users] Epetra - Dense Matrix-Vector multiply basics

Mon Apr 6 08:24:56 MDT 2015

Dear Michael:

thanks for your response.
I thought that maybe reading in overlapping chuncks of the text file using
MPI I/O might work. But I never implemented it, so I don't know how it
would actually perform. I will look into HDF5 more thoroughly.

I have one more question in terms of the data distribution.
Say a sparse matrix has some very dense columns or rows. In that case a
processor could be assigned substantially more work then everyone else
creating a bottleneck for the algorithm.
How does Epetra deal with this situation?

I've encountered the following issues:
i) Assigning columns and rows randomly may not work too well, say if there
is only one completely dense column than the processor that gets it has
more work then anyone else.
ii) Coming up with an optimal load balance is NP hard.
iii) Splitting data according to number of non-zeros will require columns
or rows to be split between processors, which would violate the unique
global ID (GID) requirement of Epetra.

Thanks a lot!
Best,
Gyorgy

On Mon, Apr 6, 2015 at 12:08 AM, Heroux, Mike <MHeroux at csbsju.edu> wrote:

>  Gyorgy,
>
>  The Matrix Market I/O functions are parallel, but only process 0 reads
> from the file.  The file contents are used to construction an Epetra object
> on process 0, which is then exported to a distributed object that is split
> across all processes according to an Epetra map.  The default map splits
> the data by a uniform distribution.  You can prescribe your own
> distribution too.
>
>  This is the only portable approach to I/O that I know of for reading and
> writing a plain text file.
>
>  In general, text-based file I/O from a single file is not very
> scalable.  It’s primarily meant as a way to enable problem studies.  You
> would probably be better off using the HDF5 functionality from EpetraExt.
>
>  Mike
>
>   From: Gyorgy Matyasfalvi <matyasfalvi at gmail.com>
> Date: Sunday, April 5, 2015 at 10:52 AM
> To: "maherou at sandia.gov" <maherou at sandia.gov>
> Cc: "trilinos-users at software.sandia.gov" <
> trilinos-users at software.sandia.gov>
> Subject: Re: [Trilinos-Users] Epetra - Dense Matrix-Vector multiply basics
>
>   Dear Michael:
>
>  thanks for your response. Ok that makes sense.
> One more question I have in terms of the MatrixMarket I/O routines.
> To me it seems that the MatrixMarketFileToCrsMatrix in EpetraExt is
> actually a serial operation since only processor 0 does the data read-in
> and then broadcasts the data to the other processors. Is that correct?
>
>  Thanks! Best,
> Gyorgy
>
> On Sat, Apr 4, 2015 at 8:23 PM, Heroux, Michael A <maherou at sandia.gov>
> wrote:
>
>> Gyorgy,
>>
>> I believe the operations you need are supported.  In the case of a wide
>> matrix, for either a sparse or dense matrix, you want to think about
>> storing A^T, and then apply the transpose operation to get the action of
>> A.  This is basically what I described in the previous message.
>>
>> You are also right about the square case, that doing a 2D decomposition
>> would be appropriate, and Epetra (and similarly Tpetra) is unique in its
>> support for this kind of decomposition, compared to other popular
>> libraries.  Even so, the infrastructure to support construction and
>> management of 2D decompositions can be substantially improved.
>>
>> If you need more details on what I describe in the first paragraph, let
>> me know.
>>
>> Mike
>>
>> On Apr 3, 2015, at 1:33 PM, Gyorgy Matyasfalvi <matyasfalvi at gmail.com
>> <mailto:matyasfalvi at gmail.com>> wrote:
>>
>> Dear Michael:
>>
>> We're solving the following optimization problem:
>>
>> min ||A(x^+ - x^-) - b||^2_2 + \nu * 1^T (x^+ + x^-)
>> x^+, x^- \in R^n
>>
>> s.t. x^+, x^- >= 0
>>
>> aka (LASSO) using a first order method called the Nonmonotone Spectral
>> Projected Gradient (SPG).
>> ( You can find more details in this paper:
>> http://www.optimization-online.org/DB_FILE/2015/01/4748.pdf )
>>
>> The matrix A in the objective function comes in many different forms:
>> tall, wide, square. In one of our test problems A is a wide matrix, with
>> dimensions: 19,996 rows and 1.355,191 columns.
>> Our most "expensive" operations are mtx-vec multiplies when computing the
>> objective function value or the gradient.
>>
>> What I'd like to achieve is that our code can handle matrices of
>> arbitrary form "appropriately". For example if A is wide i.e. few rows but
>> many columns then we partition A along it's columns (domain decomposition),
>> if A is tall i.e. many rows and few columns then we partition A along it's
>> rows (range decomposition). If A is square and huge than maybe do both
>> range and domain decomposition.
>> It seems to me this is actually doable for sparse matrices using the
>> Epetra_CrsMatrix class. My question is can I do this in the dense case with
>> the Epetra_MultiVector class?
>>
>> Thanks a lot for your help!
>> Best,
>> Gyorgy
>>
>> On Fri, Apr 3, 2015 at 1:24 AM, Heroux, Michael A <maherou at sandia.gov
>> <mailto:maherou at sandia.gov>> wrote:
>> Gyorgy,
>>
>> Please give me some details about your problem:  Algorithm, size of
>> matrices, type of data distribution.  Just the basics to start.
>>
>> Thanks.
>>
>> Mike
>>
>> On Apr 2, 2015, at 11:03 PM, Gyorgy Matyasfalvi <matyasfalvi at gmail.com
>> <mailto:matyasfalvi at gmail.com><mailto:matyasfalvi at gmail.com<mailto:
>> matyasfalvi at gmail.com>>> wrote:
>>
>> Dear Mike:
>>
>> Thanks for your help. Indeed I got an error code of -2 and I suspect
>> that, as you pointed out, the issue is that *this is not a row vector.
>>
>> My other question then would be: Is it possible to define a "Domain Map"
>> for Multivectors? i.e I want processors to own columns of the matrix
>> instead of rows. So basically spread out the columns among different
>> processors. I know think this is possible for sparse matrices.
>>
>> Thanks! Best,
>> Gyorgy
>>
>>
>>
>> On Thu, Apr 2, 2015 at 9:02 AM, Heroux, Michael A <maherou at sandia.gov
>> <mailto:maherou at sandia.gov><mailto:maherou at sandia.gov<mailto:
>> maherou at sandia.gov>>> wrote:
>> Gyorgy,
>>
>> Assuming your x, y and A are dense objects, you are using the correct
>> function, Multiply().  Chances are that you have some detail incorrect.
>> First you should check for error codes that are being returned.  Multiply()
>> will return integer error codes if it runs into issues:
>>
>> Int ierr = y.Multiply(...)
>>
>> If (ierr!=0) ...
>>
>> Regarding your transpose operation, if I understand the situation
>> correctly, x should also be transposed to be a row vector.  Multiply() is
>> probably complaining about this.  There is no way in the Epetra framework
>> to specify that the "this" argument is transposed.
>>
>> I think it is best to perform the transpose operation as
>>
>> x = A^T y
>>
>> This expression keeps the dimensions correct.
>>
>> Try this and see how it goes.
>>
>> Mike
>>
>> From: Gyorgy Matyasfalvi <matyasfalvi at gmail.com<mailto:
>> matyasfalvi at gmail.com><mailto:matyasfalvi at gmail.com<mailto:
>> matyasfalvi at gmail.com>><mailto:matyasfalvi at gmail.com<mailto:
>> matyasfalvi at gmail.com><mailto:matyasfalvi at gmail.com<mailto:
>> matyasfalvi at gmail.com>>>>
>> Date: Wednesday, April 1, 2015 at 10:41 PM
>> To: "trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov><mailto:
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov>><mailto:
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov><mailto:
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov>>>" <
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov><mailto:
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov>><mailto:
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov><mailto:
>> trilinos-users at software.sandia.gov<mailto:
>> trilinos-users at software.sandia.gov>>>>
>>  Subject: [EXTERNAL] [Trilinos-Users] Epetra - Dense Matrix-Vector
>> multiply basics
>>
>> Dear Developers/Users:
>>
>> I have a question concerning matrix-vector multiplies:
>>
>> 1) Is there a document or example file that explains the basics of
>> matrix-vector multiplies? Preferably isolated examples of mtx-vec mults.
>> instead of being embedded in some algorithm.
>>
>> If this doesn't exist. Then I'd be interested in finding out:
>>
>> 2) How to do dense matrix, dense vector multiplies?
>> I assume it's done via the Epetra_MultiVector class. However, the only
>> operation that seems to have an effect is the following:
>>
>> y = A x
>> using
>> y.Multiply('N', 'N', 1.0, A, x, 0.0)
>> (x was constructed using an Epetra_LocalMap
>> A, and y were constructed using the same Epetra_Map)
>>
>> The problem is that if I want to compute for example:
>>
>> x = y^T A
>> using
>> x.Multiply('T', 'N', 1.0, y, A, 0.0)
>>
>> it seems the Multiply() operation doesn't do anything x remains unchanged.
>>
>> What am I doing incorrectly here?
>> Thanks a lot! Best,
>> Gyorgy
>>
>>
>>
>>
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://software.sandia.gov/pipermail/trilinos-users/attachments/20150406/07eefebf/attachment.html>