Re: [ublas] Computing sparse A'A.........

From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2007-02-13 11:32:26

Gunter Winkler wrote:

>Am Dienstag, 13. Februar 2007 00:28 schrieb 
>Richard_Harding_at_[hidden]:
>  
>
>>Hello,
>>
>>I have a very sparse matrix (<= 6 nnz entries per row with
>>potentially thousands of columns) which I need to pre-multiply by its
>>transpose in order to solve the normal equations associated with a
>>least-squares computation: (A'A)x = A'b. I may have missed them, but
>>    
>>
>
>Don't do this - trust me ;-)
>
>in order to solve the least squares problem you do a QR-decomposition of 
>A and get the cholesky decomposition of A'A for free:
>
>A = QR -> A'A = (QR)'QR = R'Q'QR= R'R 
>  
>

True. But you need a sparse QR factorization. It exists, but I do not 
recall precisely where you can find code. A sparse QR can be done with a 
sparse Gram-Schmidt routine. Needless to say that fill-in is going to 
grow. Developing an efficient code using BLAS 3 etc is quite a job.

Karl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm