Speedup of random indesing of sparse matrices (comparison to scilab)

[John W. Eaton]

On  9-Oct-2007, David Bateman wrote:

| In the thread
| 
| 
http://groups.google.com/group/comp.soft-sys.math.scilab/browse_thread/thread/abc4b68e7a782163
| 
| on the scilab newsgroup I notice a comparison with one of the sparse
| indexing operations between scilab and Octave. In general Octave
| compares well, except for one particular case. This case is
| 
| rand("state",1);A = sprand(1e5,1e5,8/1e5); I = 1 +
| floor(1e5*rand(1e3,1)); J = 1 + floor(1e5*rand(1e3,1)); t0 = cputime();
| for i=1:10, B = A(I,J); end; cputime() - t0
| 
| This is about 25 times slower in Octave than Scilab and a similar amount
| than Matlab.. The permutation case is more common, but I thought I
| couldn't let stand such a big time difference with Scilab..
| 
| The attached patch tries to address this by eliminating a loop in the
| two index version of Sparse<T>::index at the expense of maintaining a
| linked list of output column indexes that point to the same columns in
| the original matrix.
| 
| Before this change I see the time 1.0048 seconds for the above operation
| and after the change I see the time 0.024996 seconds for a comparable
| time to matlab and octave.
| 
| To check the accuracy of the code I ran the above on 2.9.14, and saved
| the result with
| 
| save -binary test1.mat B
| 
| then ran the same test in 2.9.14+ with this patch, and then did
| 
| B2 = B;
| load test1.mat
| assert (B, B2)
| 
| The result was a perfect match... I also ran the above example through
| octave running over valgrind with no errors flagged. I therefore
| consider that this patch functions as desired..

Please check in this change.

Thanks,

jwe