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 ?