[petsc-users] Pseudoinverse of a large matrix

[Chetan Jhurani]

Jack,

 

The RRQR for sparse matrices comment was for generalizing the script

if anyone else wanted to use it for serious business.

 

My personal experience (and very qualitative here) with this package

http://www.cise.ufl.edu/research/sparse/SPQR/, which also has

easy to use Matlab wrappers, is that RRQR does lead to larger fill-in

for 2D and 3D 9/27 point stencils compared to LU, for example.

But it was faster than dense QR once the matrix size increased beyond

a few hundreds. To repeat the well-known - it heavily depends on the

original pattern.

 

SPQR is for shared memory, and it's likely that you knew about it already.

 

Chetan

 

 

From: petsc-users-bounces at mcs.anl.gov [mailto:petsc-users-bounces at mcs.anl.gov] On Behalf Of Jack Poulson
Sent: Monday, December 19, 2011 11:50 AM
To: PETSc users list
Subject: Re: [petsc-users] Pseudoinverse of a large matrix

 

Chetan,

I completely agree that (rank-revealing) QR should be the first choice. As a side note, from what he has said, his matrix is
actually dense. 

If his matrix was sparse, I am not sure how much sparsity would be lost by the column pivoting inherent in a rank-revealing QR. I
know that the MUMPS group is either working on or has finished a sparse QR, but I don't know any details about their approach to
pivoting (though I would be very interested!). Hopefully it could simply reuse the threshold approach used for sparse LU and LDL.

Jack

On Mon, Dec 19, 2011 at 1:38 PM, Chetan Jhurani <chetan.jhurani at gmail.com> wrote:

> It can be further optimized using the Woodbury identity for two cases -

> rank <= size or rank >= size to reduce the size of auxiliary internal Cholesky solve.

 

Sorry, that's wrong.  I meant rank <= size/2 or rank >= size/2.  Size here

refers to square matrix size, but this analysis can be done for rectangular

case too.

 

Chetan

 

From: Chetan Jhurani [mailto:chetan.jhurani at gmail.com] 
Sent: Monday, December 19, 2011 11:35 AM
To: 'PETSc users list'
Subject: RE: [petsc-users] Pseudoinverse of a large matrix

 

 

Couple of optimizations not there currently.

 

1.   It can be changed to use sparse RRQR factorization for sparse input matrix.

2.   It can be further optimized using the Woodbury identity for two cases -

rank <= size or rank >= size to reduce the size of auxiliary internal Cholesky solve.

 

Chetan

 

 

From: petsc-users-bounces at mcs.anl.gov [mailto:petsc-users-bounces at mcs.anl.gov] On Behalf Of Modhurita Mitra
Sent: Monday, December 19, 2011 11:01 AM
To: PETSc users list
Subject: Re: [petsc-users] Pseudoinverse of a large matrix

 

I am trying to express the radiation pattern of an antenna in terms of spherical harmonic basis functions. I have radiation pattern
data at N=324360 points. Therefore, my matrix is spherical harmonic basis functions evaluated till order sqrt(N) (which makes up at
total of N elements), evaluated at N data points. So this is a linear least squares problem, and I have been trying to solve it by
finding its pseudoinverse which uses SVD. The elements of the matrix are complex, and the matrix is non-sparse. I have solved it in
MATLAB using a subsample of the data, but MATLAB runs out of memory while calculating the SVD at input matrix size 2500 X 2500. I
need to solve this problem using the entire data.



I was thinking of using SLEPc because I found a ready-to-use code which computes the SVD of a complex-valued matrix (
http://www.grycap.upv.es/slepc/documentation/current/src/svd/examples/tutorials/ex14.c.html ). I don't know how to use either PETSc
or SLEPc (or Elemental) yet, so I am trying to figure out where to start and what I should learn.   

Thanks,
Modhurita

On Mon, Dec 19, 2011 at 12:31 PM, Matthew Knepley <knepley at gmail.com> wrote:

On Mon, Dec 19, 2011 at 12:21 PM, Modhurita Mitra <modhurita at gmail.com> wrote:

Hi,

I have to compute the pseudoinverse of a 324360 X 324360 matrix. Can PETSc compute the SVD of this matrix without parallelization?
If parallelization is needed, do I need to use SLEPc?

 

With enough memory, yes. However, I am not sure you want to wait. I am not sure how SLEPc would help here.

>From the very very little detail you have given, you would need parallel linear algebra, like Elemental. However,

I would start out from a more fundamental viewpoint. Such as replacing "compute the psuedoinverse" with

"solve a least-squares problem" if that is indeed the case.

 

   Matt

 


Thanks,
Modhurita





 

-- 
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/20111219/65388f1a/attachment.htm>