Jacobi Eigenvalues Efficiently

Improvement in Jacobi Matrix Transforms

Since the Jacobi matrix is mostly zero, we can save some computer time by avoiding fetching the elements that are zero and multiplying them. The following documents how to do that. First we look at multiplication from the left in a 3x3 matrix.

$\begin{array}{l} (\begin{matrix} c & 0 & s \\ 0 & 1 & 0 \\ - s & 0 & c \end{matrix}) (\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}) = (\begin{matrix} c a_{11} + s a_{31} & c a_{12} + s a_{32} & c a_{13} + s a_{33} \\ a_{21} & a_{22} & a_{23} \\ c a_{31} - s a_{11} & c a_{32} - s a_{12} & c a_{33} - s a_{13} \end{matrix}) = \\ (\begin{matrix} a_{11} + (c - 1) a_{11} + s a_{31} & a_{12} + (c - 1) a_{12} + s a_{32} & a_{13} + (c - 1) a_{13} + s a_{33} \\ a_{21} & a_{22} & a_{23} \\ a_{31} + (c - 1) a_{31} - s a_{11} & a_{32} + (c - 1) a_{32} - s a_{12} & a_{33} + (c - 1) a_{33} - s a_{13} \end{matrix}) = \\ (\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}) + (\begin{matrix} (c - 1) a_{11} + s a_{31} & (c - 1) a_{12} + s a_{32} & (c - 1) a_{13} + s a_{33} \\ 0 & 0 & 0 \\ (c - 1) a_{31} - s a_{11} & (c - 1) a_{32} - s a_{12} & (c - 1) a_{33} - s a_{13} \end{matrix}) \end{array}$

(1.1)

Note that only two rows are modified even for an nxn matrix. So we just compute those two rows and add them to A.

If c and s are in the 1^st and 3rd rows, then, for the 1^st row, we multiply the first row by (c-1) and multiply the third row by s and add these two colums, For the third row we multiply the third row by (c-1) and the first row by $-$ s and add these two rows.

Translating this to a larger matrix when c,s are in the i,j rows, for the ith row, we multiply the ith row by (c-1) and the jth row by s and add. For the jth row, we multiply the jth row by (c-1) and the ith row by $-$ s and then add these two rows.

Then we add the resulting two rows to the ith and jth rows of A and that becomes the result for this matrix multiplication.

Next consider the multiplication of matrix A times the right side Jacobi matrix.

$\begin{array}{l} (\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}) (\begin{matrix} c & 0 & - s \\ 0 & 1 & 0 \\ s & 0 & c \end{matrix}) = (\begin{matrix} a_{11} c + a_{13} s & a_{12} & a_{13} c - a_{11} s \\ a_{21} c + a_{23} s & a_{22} & a_{23} c - a_{21} s \\ a_{31} c + a_{33} s & a_{32} & - a_{31} s + a_{33} c \end{matrix}) = \\ (\begin{matrix} a_{11} + a_{11} (c - 1) + a_{13} s & a_{12} & a_{13} + a_{13} (c - 1) - a_{11} s \\ a_{21} + a_{21} (c - 1) + a_{23} s & a_{22} & a_{23} + a_{23} (c - 1) - a_{21} s \\ a_{31} + a_{31} (c - 1) + a_{33} s & a_{32} & a_{33} - a_{31} s + a_{33} (c - 1) \end{matrix}) = \\ (\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}) + (\begin{matrix} a_{11} (c - 1) + a_{13} s & 0 & a_{13} (c - 1) - a_{11} s \\ a_{21} (c - 1) + a_{23} s & 0 & a_{23} (c - 1) - a_{21} s \\ a_{31} (c - 1) + a_{33} s & 0 & a_{33} (c - 1) - a_{31} s \end{matrix}) \end{array}$

(1.2)

Note that only 2 columns are modified even for an nxn matrix.

If c and s are in the 1^st and 3rd rows, then, for the 1^st column, we multiply the first column by (c-1) and multiply the third column by s and add these two colums, For the third column we multiply the third column by (c-1) and the first column by $-$ s and add these two columns.

Translating this to a larger matrix when c,s are in the i,j rows, for the ith column, we multiply the ith column by (c-1) and the jth column by s and add. For the jth column, we multiply the jth column by (c-1) and the ith column by $-$ s and then add these two columns.

Then we add the resulting two columns to the ith and jth columns of A and that becomes the result for this matrix multiplication.

Just to convince the reader we do the left multiplication for rows 2 and 3 in a 4x4 matrix.

$(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & c & s & 0 \\ 0 & - s & c & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) (\begin{matrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix}) = (\begin{matrix} a_{11} & a_{12} & a_{13} & a_{14} \\ c a_{21} + s a_{31} & c a_{22} + s a_{32} & c a_{23} + s a_{33} & c a_{24} + s a_{34} \\ c a_{31} - s a_{21} & c a_{32} - s a_{22} & c a_{33} - s a_{23} & c a_{34} - s a_{24} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix})$

$\begin{array}{l} (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & c & s & 0 \\ 0 & - s & c & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) (\begin{matrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix}) = \\ (\begin{matrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix}) + (\begin{matrix} a_{11} & a_{12} & a_{13} & a_{14} \\ (c - 1) a_{21} + s a_{31} & (c - 1) a_{22} + s a_{32} & (c - 1) a_{23} + s a_{33} & (c - 1) a_{24} + s a_{34} \\ (c - 1) a_{31} - s a_{21} & (c - 1) a_{32} - s a_{22} & (c - 1) a_{33} - s a_{23} & (c - 1) a_{34} - s a_{24} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix}) \end{array}$ (1.3)

Note that only rows 2 and 3 are changed.