Re: Finding maximum of an array

"Richard Lavoie" <somone@xxxxxxxxxxxxx> wrote:

1. Create an array of integers equal in length to the number of rows
and populate it with -1's. -1 will be a flag that you haven't found
the minimum of the corresponding row. I'll call this array
IndexArray.
2. loop over the rows and find the minimum of each row. Place the
index of that minimum in IndexArray.
3. After deleting the column decrement all in the members of
IndexArray that are higher than the column that was deleted and change
the numbers in IndexArray that are equal to the column that was
deleted to -1
4. When searching for the minimum of a row again, check IndexArray
first. If the number in IndexArray is >= 0, that is the position of
the minimum and you don't have to search that row. Only search a row
if the corresponding member of IndexArray is -1.


I'm not sure about the other ones, so here are what I try to achieve.

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).

Hope this help

Richard






.