6
$\begingroup$

Cross posted on StackOverflow.

I have some extremely large sparse matrices created using spMatrix function from the matrix package.

Using the solve() function works for my Ax=b issue, but it takes a very long time. Several days.

I noticed that http://cran.r-project.org/web/packages/RScaLAPACK/RScaLAPACK.pdf appears to have a function that can parallelize the solve function, however, it can take several weeks to get new packages installed on this particular server.

The server already has the snow package installed it.

So

  • Is there a way of using snow to parallelize this operation?
  • If not, are there other ways to speed up this type of operation?
  • Are there other packages like RScaLAPACK? My search on RScaLAPACK seemed to suggest people had a lot of issues with it.

Thanks.

Additional details

  • The matrices are about 370,000 x 370,000. I'm using it to solve for alpha centrality, http://en.wikipedia.org/wiki/Alpha_centrality.
  • I was originally using the alpha centrality function in the igraph package, but it would crash R.
  • This is on a single machine with 12 cores and 96 gigs of memory (I believe)
  • It's a directed graph along the lines of paper citation relationships.
  • Calculating condition number and density will take awhile. Will post as it comes available.
Improve this question
$\endgroup$
3
  • $\begingroup$ By the way, you can bound the condition number, without having to calculate the smallest eigenvalue. In fact, if the matrix is singular, then it won't be full rank and the condition number won't be that helpful. Perhaps you can report the first K eigenvalues - where K is something that isn't too time-consuming to calculate. $\endgroup$
    – Iterator
    Oct 29, 2011 at 20:04
  • $\begingroup$ @mbq It was my suggestion that he cross post, though I'd not intended for the identical question to be posted. :) On SO, I tried to address more computational aspects of the question (e.g. suggesting changing the BLAS library), with a bit of statistical advice; I think that this site is where one can get the statistical issues addressed. I think the question should've been asked differently here - along the lines of what changes in the statistical method could be used to improve the computational efficiency. $\endgroup$
    – Iterator
    Oct 30, 2011 at 3:46
  • 2
    $\begingroup$ (Continued) As we're seeing, the suggestions by Mike and whuber are far different than one would normally see on SO. FWIW, I think that changing the statistical calculation will yield the best speedups, while changing the backend math libraries will also substantially speed up the calculations (perhaps a good 12X-36X speedup, given the infrastructure, by changing the libraries, and potentially much more than that by changing the statistical methods). $\endgroup$
    – Iterator
    Oct 30, 2011 at 3:47

2 Answers 2

Reset to default
3
$\begingroup$

You can decompose this operation into a set of smaller operations that are easy to parallelize.

Suppose you wish to solve $\mathbf{m}\mathbf{v}=\mathbf{u}$ for an $N$ by $N$ matrix $\mathbf{m}$ and $N$-vector $\mathbf{u}$. Writing $N=n+m$ (intending $n\approx m$), decompose $\mathbf{m}$ into four blocks $\mathbf{a}_{n \times n}$, $\mathbf{b}_{n \times m}$, $\mathbf{c}_{m\times n}$, and $\mathbf{d}_{m \times m}$, and also decompose $\mathbf{u}$ into its first $n$ components $\mathbf{e}_n$ and its last $m$ components $\mathbf{f}_m$ while similarly expressing $\mathbf{v}$ as the concatenation of the $n$-vector $\mathbf{x}$ and the $m$-vector $\mathbf{y}$. The original system is readily seen to be equivalent to the sequence

$$\eqalign{ \mathbf{a} \mathbf{z} &= \mathbf{e} \\ \mathbf{a} \mathbf{w} &= \mathbf{b} \\ \left(\mathbf{d}-\mathbf{c}\mathbf{w}\right)\mathbf{y}& = \mathbf{f} - \mathbf{c}\mathbf{z} \\ \mathbf{a}\mathbf{x} &= \mathbf{e} - \mathbf{b}\mathbf{y} }$$

The first two form $m+1$ systems of $n$ equations (having a common matrix); the third is a single system of $m$ equations (depending on the solutions to the first two); and the last is a single system of $n$ equations (depending on the solution to the third). By choosing $m \approx n \approx N/2$, you have reduced the sizes of the matrices involved and you have created an opportunity to run the first $m+1$ systems in parallel. If this is not enough, the technique can be applied recursively.

This approach works no matter what algorithm for solving a linear system you may favor.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This looks promising. I'm going to try to implement this and farm it out to r processes using snow. I'll report back. $\endgroup$
    – Robert
    Oct 30, 2011 at 2:42
  • 2
    $\begingroup$ @Robert Out of curiosity, how did the implementation work out? $\endgroup$
    – Iterator
    Dec 31, 2011 at 16:04
3
$\begingroup$

Have you tried QR decomposition? See Theorem 3 here for solving $Ax=b$.

Finding the inverse of a matrix (even a small one) is a slow process. Methods such as QR or Cholesky decomposition are used in practice when 'inverting' is needed (at least in my experience in statistical programming).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This looks good too. Will try it and see how it compares to the algo above. $\endgroup$
    – Robert
    Oct 30, 2011 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.