At elimination column , let be the size of the remaining trailing block. Computing its multipliers costs divisions; updating all entries costs floating-point operations, one multiplication and one subtraction per entry. Thus the dominant count isUpdating the right side and back substitution add only floating-point operations. Pivot searches involve comparisons and row exchanges, without changing the leading arithmetic count. Hence Gaussian elimination with pivoting has the requested asymptotic cost.
An orthogonal similarity transformation is with . An upper Hessenberg matrix has whenever ; its first subdiagonal may be nonzero.
At step , choose a Householder reflector whose trailing block sends the current column segment in rows to a multiple of its first coordinate. The left multiplication zeros positions . Apply the matching right multiplication to retain similarity: . Since acts only on rows and columns , earlier Hessenberg zeros are preserved. Finally gives .
Each reflector is applied through a rank-one update, costing rather than a full matrix multiplication. Across steps, the Hessenberg reduction costs .
Solving the unrelated shifted systems by separate Gaussian elimination costs floating-point operations.
Instead compute once in work. For each shift, solveThe shift changes only the diagonal, so remains an upper Hessenberg matrix. In each elimination column only the entry immediately below the pivot needs removal. With partial pivoting the only possible nonzero candidate rows are the current row and the next, and each update touches entries. Factorization therefore costs per shift; the triangular solve and both orthogonal-vector transformations also cost each.
Thus shifted solves plus the initial Hessenberg reduction cost in total. Pivoting is still needed in general: nonsingularity excludes a singular system but does not by itself guarantee that every unpivoted elimination pivot is nonzero.
Articles by others on the same topic
There are currently no matching articles.