What is the most efficient algorithm for finding a row of a matrix which matches a given row? This is the same as a table lookup based on multiple criteria.
Finite Element Matrices are usually large and sparse, so storing the entire matrix in memory is an inefficient use of computer memory. As such, I am generating the matrices as 3-tuples i.e. (row index, column index, matrix value). Due to the unstructured nature of the underlying grid, the same matrix element may need to be incremented a number of times.
To achieve this, the existing elements must be searched to see if the (row,column) pair already exists. If it does, then the value can be incremented. If it doesn't, a new 3-tuple is created for the new non-zero value of the matrix.
My question is: what is an efficient method for checking if the (row,column) pair already exists? And if it does, what the index into the array is?
This is essentially the same as finding a row of a matrix which matches a given row.
Currently, this is implemented in MATLAB as
% rw is the array of row indices % cl is the array of column indices % rv is the row being searched for % cv is the column being searched for % i.e. searching for (rv,cv) in (rw,cl) possible_row = find(rw == rv); column = find(cl(possible_row) == cv); % check that it was found first if isempty(column) % doesn't exist yet element_index = -1; % flag that it needs to be created else element_index = possible_row(column); end % return element_index
Due to the nature of
find, this procedure is much faster than manually looping through the array. I could write a MEX function to do this, but I would prefer not to at this stage.
Any help will be greatly appreciated.