Re: [ublas] Size problem in operations on sparse matrices

From: Gunter Winkler (guwi17_at_[hidden])
Date: 2007-03-02 07:51:09

On Friday 02 March 2007 13:34, Sourabh wrote:
> Is it true even if the matrix (which I want inverse of) is lower
> triangular and sparse ? 

I don't know, do you?

> Actually I have a decision to make. I have a 
> matrix of constant values, If I don't
> take inverse of that matrix, I have to solve the set of linear equations
> many
> times. On the other hand, if I take inverse of the matrix, I can compute
> the values (A * inv (X) + Y) once and store the matrix. (The size of X is
> 1e7).  I am unable to decide which way will be faster or feasible in terms
> of storage and run time complexity ?
>
> Could you please help me in deciding this ?

I'll try. You just have to count the flops (see any good book about numerical 
linear algebra, e.g. Golub/van Loan)

n ... size of matrix/vector
npr ... nonzeros per row
nnz = n * npr (approximately)

sparse triangular solve with dense right hand side: O(n * npr)
sparse matrix times dense vector: O(nnz)
However if the nnz of inv(X) is n^2 then the solver always wins.

mfg
Gunter