Jesse L. Barlow

Nevena Jakovcevic Stor, Ivan Slapnicar, Jesse L. Barlow

We present a new algorithm for solving an eigenvalue problem for a real symmetric arrowhead matrix. The algorithm computes all eigenvalues and all components of the corresponding eigenvectors with high relative accuracy in $O(n^{2})$ operations. The algorithm is based on a shift-and-invert approach. Double precision is eventually needed to compute only one element of the inverse of the shifted matrix. Each eigenvalue and the corresponding eigenvector can be computed separately, which makes the algorithm adaptable for parallel computing. Our results extend to Hermitian arrowhead matrices, real symmetric diagonal-plus-rank-one matrices and singular value decomposition of real triangular arrowhead matrices.

Jesse L. Barlow, Alicja Smoktunowicz

A new reorthogonalized block classical Gram--Schmidt algorithm is proposed that factorizes a full column rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular and nonsingular. With appropriate assumptions on the diagonal blocks of $R$, the algorithm, when implemented in floating point arithmetic with machine unit $\macheps$, produces $Q$ and $R$ such that $\| I- Q^{T} Q \|_2 =O(\macheps)$ and $\| A-QR \|_2 =O(\macheps \| A \|_2)$. The resulting bounds also improve a previous bound by Giraud et al. [Num. Math., 101(1):87-100,\ 2005] on the CGS2 algorithm originally developed by Abdelmalek [BIT, 11(4):354--367,\ 1971]. \medskip Keywords: Block matrices, Q--R factorization, Gram-Schmidt process, Condition numbers, Rounding error analysis.

Nevena Jakovcevic Stor, Ivan Slapnicar, Jesse L. Barlow

We present a new algorithm for solving an eigenvalue problem for a real symmetric matrix which is a rank-one modification of a diagonal matrix. The algorithm computes each eigenvalue and all components of the corresponding eigenvector with high relative accuracy in $O(n)$ operations. The algorithm is based on a shift-and-invert approach. Only a single element of the inverse of the shifted matrix eventually needs to be computed with double the working precision. Each eigenvalue and the corresponding eigenvector can be computed separately, which makes the algorithm adaptable for parallel computing. Our results extend to the complex Hermitian case. The algorithm is similar to the algorithm for solving the eigenvalue problem for real symmetric arrowhead matrices from: N. Jakovčević~Stor, I. Slapničar and J. L. Barlow, {Accurate eigenvalue decomposition of real symmetric arrowhead matrices and applications}, Lin. Alg. Appl., 464 (2015).

Alicja Smoktunowicz, Jesse L. Barlow, Julien Langou

An error analysis result is given for classical Gram--Schmidt factorization of a full rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular. The work presented here shows that the computed $R$ satisfies $\normal{R}=\normal{A}+E$ where $E$ is an appropriately small backward error, but only if the diagonals of $R$ are computed in a manner similar to Cholesky factorization of the normal equations matrix. A similar result is stated in [Giraud at al, Numer. Math. 101(1):87--100,2005]. However, for that result to hold, the diagonals of $R$ must be computed in the manner recommended in this work.