Re: [ublas] Solving linear equations in a loop (Optimization issues)

From: Sourabh (sourabh_at_[hidden])
Date: 2007-03-03 07:52:51

On Sat, 3 Mar 2007, Gunter Winkler wrote:

> Sourabh schrieb:
> > Hi Gunter, 
> > Thanks for your kind reply.
> > The structure of my matrices are as follows :
> >
> > X is a lower triangular matrix of size (100 x 100) (in addtion, all 
> > diagonal elements are also 
> > zero), with at most 3 or 4 non-zero entries per column.
> >   
> So, I suggest using a compressed_matrix which will hold (-lembda)
> > What is your opinion, is construction of these matrices take much of the 
> > time ? 
> >   
> construction is usually expensive, because you have to allocate storage 
> and (sometimes) initialize some values. Thus I would move all 
> constructions out of the loop. A call of the  clear() member function is 
> very cheap (only a few integer assigements). When you fill the matrix in 
> order (row by row for a row_major matrix) using push_back(i,j,value) you 
> gain optimal speed.
> > I need to solve  the equation    (I-lembda) slopes = omegas
> >   
> then you should initialize the matrix with (-lemda) and use the unit 
> lower triangular solver ("unit" means the diagonal elements are treated 
> as they were 1.0)
> 
> > Same question as above. The delays vector creation or assignment to delays 
> > in each loop?
> >   
> the creation need a call to new() which is always expensive. The 
> assignement has to occure anyway. So construct the vector before. (You 
> additionally improve the locality because the memory of this vector is 
> already inside the cache).
> > Thank you very much for your help.
> You could write a simple program with similar data and post it here. So 
> we can add it to the examples and benchmark collection.
> 
> mfg
> Gunter
> 

I just want to discuss the algorithmic complexity of the program. I want 
to separate out the time take by the algorithm and by the way algo is 
implemented. 

I am doing the following steps 2e9 times. 
1. Creating A = I - lembda (lembda, A are 100 x 100 sparse lower 
triangular matrix with around 300 non-zero entries). 

Time taken will be of order of 300 instructions

2. Solve AX = B ( A is 100 x 100 sparse lower triangular matrix with 
around 300 non-zero entries).

The order of this should be 300 instructions. 

3. Getting Y = C X ( C is similar (not identical) to A.

4. Y += D. ( D is dense vector of 100). 

These 4 steps should not be taking so much time if repeated 2e9 times 
(not more than some hours), or am I missing 
something ?