Re: Finding maximum of an array

Richard Lavoie wrote:

I need to perform a hierarchical clustering from a distance matrix. I
have a huge matrix of single values all between 0 and 1and I am
looking for the highest value. It is a diagonal matrix so I don't
look at every cells but only at the upper diagonal.
I get the coordinates of the highest value, transform some values in
the matrix and then delete the corresponding row and columns. I then
repeat the operation until I end up with a small matrix of 1 x 1.

I may start with a 4000 x 4000 matrix, and reduce the dimension 3999
times, every time looking at the maximum value and then removing the
row and column.

About 45% of the time is spent deleting rows and column, and 45%
finding the maximum value (about 10% computing other things).


Will the transformations change the order of the individual rows and
columns? If not, you should be able to sort the 4000 numbers once (keeping
their original index associated), and then loop through that vector once and
do all the transformations.

Depending on how you store the matrix and how a 'delete row'/'delete column'
operation looks, it might be possible to make that 45% smaller by using a
vector of 'active rows' and one of 'active columns'. Then the 'delete row'
operation is equal to 'remove one value from a vector'. OTOH, this increases
the time for each matrix access a small amount, so it may not be worth it.

--
Anders Isaksson, Sweden
BlockCAD: http://web.telia.com/~u16122508/proglego.htm
Gallery: http://web.telia.com/~u16122508/gallery/index.htm


.