# Finding the Maximum Value from a Matrix-Vector Multiplication

I'm performing a typical matrix vector multiplcation, where the matrix is symmetric, and the vector is sparse. After multiplication I am then only using the absolute maximum value from the resulting vector in further calculations.

My question is, is there some sort of method that will allow me to find out which row of the matrix will be producing the corresponding maximum value in the resulting vector, so that I will only need to perform a single row*column multiplication?

-
If the number of rows is $R$ and the number of entries in the vector is $C$, in general you need to look at $RC$ entries of the matrix, so the algorithm is going to do at least $RC$ operations. Your algorithm does $RC$ multiplications and $R(C-1)$ additions, $R$ absolute values and $R-1$ comparisons. Do you really expect anything better? –  Yuval Filmus Jan 25 '11 at 5:06