<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 12 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Verdana;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
{mso-style-priority:99;
mso-style-link:"Balloon Text Char";
margin:0in;
margin-bottom:.0001pt;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Verdana","sans-serif";
color:windowtext;}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>Jack,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>The RRQR for sparse matrices comment was for generalizing the script<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>if anyone else wanted to use it for serious business.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>My personal experience (and very qualitative here) with this package<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><a href="http://www.cise.ufl.edu/research/sparse/SPQR/">http://www.cise.ufl.edu/research/sparse/SPQR/</a>, which also has<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>easy to use Matlab wrappers, is that RRQR does lead to larger fill-in<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>for 2D and 3D 9/27 point stencils compared to LU, for example.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>But it was faster than dense QR once the matrix size increased beyond<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>a few hundreds. To repeat the well-known - it heavily depends on the<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>original pattern.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>SPQR is for shared memory, and it’s likely that you knew about it already.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>Chetan<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'><o:p> </o:p></span></p><div style='border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt'><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> petsc-users-bounces@mcs.anl.gov [mailto:petsc-users-bounces@mcs.anl.gov] <b>On Behalf Of </b>Jack Poulson<br><b>Sent:</b> Monday, December 19, 2011 11:50 AM<br><b>To:</b> PETSc users list<br><b>Subject:</b> Re: [petsc-users] Pseudoinverse of a large matrix<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'>Chetan,<br><br>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. <br><br>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.<br><br>Jack<o:p></o:p></p><div><p class=MsoNormal>On Mon, Dec 19, 2011 at 1:38 PM, Chetan Jhurani <<a href="mailto:chetan.jhurani@gmail.com">chetan.jhurani@gmail.com</a>> wrote:<o:p></o:p></p><div><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>> It can be further optimized using the Woodbury identity for two cases –</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>> rank <= size or rank >= size to reduce the size of auxiliary internal Cholesky solve.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>Sorry, that’s wrong. I meant rank <= size/2 or rank >= size/2. Size here</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>refers to square matrix size, but this analysis can be done for rectangular</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>case too.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>Chetan</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p><div style='border:none;border-left:solid windowtext 1.5pt;padding:0in 0in 0in 4.0pt;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue'><div><div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0in 0in 0in;border-color:-moz-use-text-color -moz-use-text-color'><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> Chetan Jhurani [mailto:<a href="mailto:chetan.jhurani@gmail.com" target="_blank">chetan.jhurani@gmail.com</a>] <br><b>Sent:</b> Monday, December 19, 2011 11:35 AM<br><b>To:</b> 'PETSc users list'<br><b>Subject:</b> RE: [petsc-users] Pseudoinverse of a large matrix</span><o:p></o:p></p></div></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>Couple of optimizations not there currently.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p><p><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>1.</span><span style='font-size:7.0pt'> </span><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>It can be changed to use sparse RRQR factorization for sparse input matrix.</span><o:p></o:p></p><p><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>2.</span><span style='font-size:7.0pt'> </span><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>It can be further optimized using the Woodbury identity for two cases –</span><o:p></o:p></p><p><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>rank <= size or rank >= size to reduce the size of auxiliary internal Cholesky solve.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'>Chetan</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif"'> </span><o:p></o:p></p></div><div style='border:none;border-left:solid windowtext 1.5pt;padding:0in 0in 0in 4.0pt;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue'><div><div><div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0in 0in 0in;border-color:-moz-use-text-color -moz-use-text-color'><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> <a href="mailto:petsc-users-bounces@mcs.anl.gov" target="_blank">petsc-users-bounces@mcs.anl.gov</a> [<a href="mailto:petsc-users-bounces@mcs.anl.gov" target="_blank">mailto:petsc-users-bounces@mcs.anl.gov</a>] <b>On Behalf Of </b>Modhurita Mitra<br><b>Sent:</b> Monday, December 19, 2011 11:01 AM<br><b>To:</b> PETSc users list<br><b>Subject:</b> Re: [petsc-users] Pseudoinverse of a large matrix</span><o:p></o:p></p></div></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'>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.<o:p></o:p></p><div><div><p class=MsoNormal><br><br>I was thinking of using SLEPc because I found a ready-to-use code which computes the SVD of a complex-valued matrix ( <a href="http://www.grycap.upv.es/slepc/documentation/current/src/svd/examples/tutorials/ex14.c.html" target="_blank">http://www.grycap.upv.es/slepc/documentation/current/src/svd/examples/tutorials/ex14.c.html</a> ). 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. <br><br>Thanks,<br>Modhurita<o:p></o:p></p></div></div><div><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>On Mon, Dec 19, 2011 at 12:31 PM, Matthew Knepley <<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>> wrote:<o:p></o:p></p><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>On Mon, Dec 19, 2011 at 12:21 PM, Modhurita Mitra <<a href="mailto:modhurita@gmail.com" target="_blank">modhurita@gmail.com</a>> wrote:<o:p></o:p></p></div><div><div><blockquote style='border:none;border-left:solid windowtext 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color rgb(204,204,204)'><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Hi,<br><br>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?<o:p></o:p></p></blockquote><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>With enough memory, yes. However, I am not sure you want to wait. I am not sure how SLEPc would help here.<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>From the very very little detail you have given, you would need parallel linear algebra, like Elemental. However,<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>I would start out from a more fundamental viewpoint. Such as replacing "compute the psuedoinverse" with<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>"solve a least-squares problem" if that is indeed the case.<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> Matt<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div><blockquote style='border:none;border-left:solid windowtext 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color rgb(204,204,204)'><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><br>Thanks,<br>Modhurita<o:p></o:p></p></blockquote></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='color:#888888'><br><br clear=all></span><o:p></o:p></p><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='color:#888888'> </span><o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='color:#888888'>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>-- Norbert Wiener</span><o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div></div></div></div></div></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>