| pseudo code for doing SVD on 2D sparse array [message #64321] |
Sun, 21 December 2008 03:41  |
erano
Messages: 22
Registered: November 2008
|
Junior Member |
|
|
Hi,
I wish to solve Ax=B
A is sparse array (size m*n), in format of [ x_index, y_index, value ]
B is vector length m
x is unknown vector length n
n=1,000,000
m=2*n
better to help with IDL code, but any idea is welcome!
Eran
|
|
|
|
| Re: pseudo code for doing SVD on 2D sparse array [message #64398 is a reply to message #64321] |
Mon, 22 December 2008 07:17  |
Evgenii Rudnyi
Messages: 1
Registered: December 2008
|
Junior Member |
|
|
On 21 дек, 17:30, spellu...@fb04373.mathematik.tu-darmstadt.de (Peter
Spellucci) wrote:
> In article < fb7c56d7-4124-4228-949b-aeb66116d...@t39g2000prh.googlegroup s.com >,
> Brian Borchers <borchers.br...@gmail.com> writes:
>
>> On Dec 21, 4:41 am, erano <eran.o...@gmail.com> wrote:
>>> Hi,
>>> I wish to solve Ax=B
>>> A is sparse array (size m*n), in format of [ x_index, y_index, value ]
>>> B is vector length m
>>> x is unknown vector length n
>>> n=1,000,000
>>> m=2*n
>
...
> without matlab:
> lsqr is available also through netlib (f77 code) but
> what about netlib/svdpack, which has code just for this problem?
> lsqr for such a large column space might run into trouble.
>
> hth
> peter
It could be easier to compile SVDLIBC rather than the original SVDPACK
http://tedlab.mit.edu/~dr/SVDLIBC/
make under Cygwin happens to be enough and then
$ ./svd -r sth -o tt dat1.txt
seems to solve the problem matrix dat1.txt from SVDPACK
A good reference to SVD where I have found the link to SVDLIBC
http://en.wikipedia.org/wiki/Singular_value_decomposition
Best wishes,
Evgenii
http://MatrixProgramming.com
|
|
|
|
| Re: pseudo code for doing SVD on 2D sparse array [message #64399 is a reply to message #64321] |
Mon, 22 December 2008 07:07 |
Jeremy Bailin
Messages: 618
Registered: April 2008
|
Senior Member |
|
|
On Dec 21, 6:41 am, erano <eran.o...@gmail.com> wrote:
> Hi,
> I wish to solve Ax=B
> A is sparse array (size m*n), in format of [ x_index, y_index, value ]
> B is vector length m
> x is unknown vector length n
> n=1,000,000
> m=2*n
>
> better to help with IDL code, but any idea is welcome!
>
> Eran
You said a couple of weeks ago that you'd gotten LINBCG to work on
this... what problems are you having with it?
-Jeremy.
|
|
|
|
| Re: pseudo code for doing SVD on 2D sparse array [message #64418 is a reply to message #64321] |
Sun, 21 December 2008 08:30 |
spellucci
Messages: 1
Registered: December 2008
|
Junior Member |
|
|
In article <fb7c56d7-4124-4228-949b-aeb66116d298@t39g2000prh.googlegroups.com>,
Brian Borchers <borchers.brian@gmail.com> writes:
> On Dec 21, 4:41 am, erano <eran.o...@gmail.com> wrote:
>> Hi,
>> I wish to solve Ax=B
>> A is sparse array (size m*n), in format of [ x_index, y_index, value ]
>> B is vector length m
>> x is unknown vector length n
>> n=1,000,000
>> m=2*n
>>
>
> The title of your posting refers to the SVD, but the body of the
> posting indicates that you want to solve a linear system of equations,
> perhaps in the least squares sense.
>
this is only the (unfortunately usual) sloppy kind to write down a
linear least squares problem
> Unfortunately, computing the SVD of your 2,000,000 by 1,000,000 sparse
> matrix is utterly impractical- it would require the storage of a
> 1,000,000 by 1,000,000 fully dense matrix and a 2,000,000 by 2,000,000
> fully dense matrix, which would take up about 2.4e13 bytes of
> storage...
>
> Finding a least squares solution to the system of equation should
> probably be done using an iterative method such as lsqr. In order to
> do this, you'll first want to convert your data into a MATLAB sparse
> matrix with
>
> As=sparse(A(:,1),A(:,2),A(:,3));
>
> Then solve with
>
> x=lsqr(As,b);
>
> Since your matrix is extremely large, this could take a long time or
> simply fail to converge. If so, you might want to loosen the default
> tolerance, introduce a preconditioner, etc. The documentation on lsqr
> explains how to do these things.
without matlab:
lsqr is available also through netlib (f77 code) but
what about netlib/svdpack, which has code just for this problem?
lsqr for such a large column space might run into trouble.
hth
peter
|
|
|
|
| Re: pseudo code for doing SVD on 2D sparse array [message #64419 is a reply to message #64321] |
Sun, 21 December 2008 06:46 |
Brian Borchers
Messages: 1
Registered: December 2008
|
Junior Member |
|
|
On Dec 21, 4:41 am, erano <eran.o...@gmail.com> wrote:
> Hi,
> I wish to solve Ax=B
> A is sparse array (size m*n), in format of [ x_index, y_index, value ]
> B is vector length m
> x is unknown vector length n
> n=1,000,000
> m=2*n
>
The title of your posting refers to the SVD, but the body of the
posting indicates that you want to solve a linear system of equations,
perhaps in the least squares sense.
Unfortunately, computing the SVD of your 2,000,000 by 1,000,000 sparse
matrix is utterly impractical- it would require the storage of a
1,000,000 by 1,000,000 fully dense matrix and a 2,000,000 by 2,000,000
fully dense matrix, which would take up about 2.4e13 bytes of
storage...
Finding a least squares solution to the system of equation should
probably be done using an iterative method such as lsqr. In order to
do this, you'll first want to convert your data into a MATLAB sparse
matrix with
As=sparse(A(:,1),A(:,2),A(:,3));
Then solve with
x=lsqr(As,b);
Since your matrix is extremely large, this could take a long time or
simply fail to converge. If so, you might want to loosen the default
tolerance, introduce a preconditioner, etc. The documentation on lsqr
explains how to do these things.
|
|
|
|
| Re: pseudo code for doing SVD on 2D sparse array [message #64470 is a reply to message #64399] |
Tue, 23 December 2008 06:58 |
erano
Messages: 22
Registered: November 2008
|
Junior Member |
|
|
On Dec 22, 5:07 pm, Jeremy Bailin <astroco...@gmail.com> wrote:
> On Dec 21, 6:41 am, erano <eran.o...@gmail.com> wrote:
>
>> Hi,
>> I wish to solve Ax=B
>> A is sparse array (size m*n), in format of [ x_index, y_index, value ]
>> B is vector length m
>> x is unknown vector length n
>> n=1,000,000
>> m=2*n
>
>> better to help with IDL code, but any idea is welcome!
>
>> Eran
>
> You said a couple of weeks ago that you'd gotten LINBCG to work on
> this... what problems are you having with it?
>
> -Jeremy.
Well, Yes and Not.
Basiclly, the LINBCG is working after the adding, but for large array
the output seems with mistakes in some rows...
so I'm looking for something better
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
