Balancing sparse matrices for computing eigenvalues (Q1976919)

At first the traditional balancing algorithm GEBAL for dense matrices contained, e.g., in the package LAPACK [see also \textit{B. Parlett} and \textit{C. Reinsch}, Numer. Math. 13, 293-304 (1969; Zbl 0184.37703)] is described. Then, for balancing sparse matrices an efficient direct algorithm based on the Parlett-Reinsch algorithm with an improved initial permutation phase is presented and suitable data structures for its implementation are discussed. Numerical examples show that this sparse balancing algorithm is faster than the algorithm for dense matrices if the density is less than 0.5. Furthermore, three probabilistic balancing algorithms which do not require a direct access to the matrix but only matrix-vector and/or matrix-transpose-vector multiplications are described. The theory behind these algorithms is discussed. Finally, all presented algorithms are compared with respect to norm reduction, running time and accuracy of the computed eigenvalues.