Skip to main content

Subsection 4.5.2 Rank Revealing Householder QR factorization

The unblocked QR factorization discussed in Section 3.3 can be supplemented with column pivoting, yielding HQRP_unb_var1 in Figure 4.5.2.1. In that algorithm, we incorporate the idea that the weights that are used to determine how to pivot can be updated at each step by using information in the partial row \(r_{12}^T \text{,}\) which overwrites \(a_{12}^T \text{,}\) just like it was in Subsection 4.5.1.

\begin{equation*} \newcommand{\routinename}{[ A, t, p ] ={\rm HQRP\_unb\_var1 }( A )} \newcommand{\initialize}{v := {\rm ComputeWeights}( A )} \newcommand{\guard}{n( A_{TL} ) \lt n( A )} \newcommand{\partitionings}{ A \rightarrow \FlaTwoByTwo{ A_{TL} } {A_{TR}} { A_{BL} } { A_{BR} } , t \rightarrow \FlaTwoByOne{ t_{T} } { t_{B} } , p \rightarrow \FlaTwoByOne{ p_{T} } { p_{B} } , v \rightarrow \FlaTwoByOne{ v_{T} } { v_{B} } } \newcommand{\partitionsizes}{ A_{TL} {\rm ~is~} 0 \times 0 {\rm ~and~} t_T {\rm ~has~} 0 {\rm ~elements}} \newcommand{\repartitionings}{ \FlaTwoByTwo{ A_{TL} } {A_{TR}} { A_{BL} } { A_{BR} } \rightarrow \FlaThreeByThreeBR{ A_{00} }{ a_{01} }{ A_{02} } { a_{10}^T }{ \alpha_{11} }{ a_{12}^T } { A_{20} }{ a_{21} }{ A_{22} } , \FlaTwoByOne{ t_{T} } { t_{B} } \rightarrow \FlaThreeByOneB{ t_{0} } { \tau_{1} } { t_{2} } , \\ \FlaTwoByOne{ p_{T} } { p_{B} } \rightarrow \FlaThreeByOneB{ p_{0} } { \pi_{1} } { p_{2} } , \FlaTwoByOne{ v_{T} } { v_{B} } \rightarrow \FlaThreeByOneB{ v_{0} } { \nu_{1} } { v_{2} } } \newcommand{\moveboundaries}{ \cdots } \newcommand{\update}{ \begin{array}{l} [ \left( \begin{array}{c} \nu_1 \\ v_2 \end{array} \right), \pi_1 ] = {\rm DeterminePivot}( \left( \begin{array}{c} \nu_1 \\ v_2 \end{array} \right) ) \\ \left( \begin{array}{c c } a_{01} \amp A_{02} \\ \hline \alpha_{11} \amp a_{12}^T \\ a_{21} \amp A_{22} \end{array} \right) := \left( \begin{array}{c c} a_{01} \amp A_{02} \\ \hline \alpha_{11} \amp a_{12}^T \\ a_{21} \amp A_{22} \end{array} \right) P( \pi_1 )^T \\ \left[ \FlaTwoByOneSingleLine { \alpha_{11} } { a_{21}}, \tau_1 \right] := \left[ \FlaTwoByOneSingleLine { \rho_{11} } { u_{21}}, \tau_1 \right] = {\rm Housev} \left( \begin{array}{c} \alpha_{11} \\ a_{21} \end{array} \right) \\ w_{12}^T := ( a_{12}^T + a_{21}^H A_{22} )/\tau_1 \\ \FlaTwoByOneSingleLine { a_{12}^T } { A_{22} } := \FlaTwoByOneSingleLine { a_{12}^T - { w_{12}^T } } { A_{22} - { a_{21} } { w_{12}^T } } \\ v_2 = {\rm UpdateWeight}( v_2, a_{12} ) \end{array} } \FlaAlgorithmWithInit \end{equation*}
Figure 4.5.2.1. Rank Revealing Householder QR factorization algorithm.

Combining a blocked Householder QR factorization algorithm, as discussed in Subsubsection 3.4.1.3, with column pivoting is tricky, since half the computational cost is inherently in computing the parts of \(R \) that are needed to update the weights and that stands in the way of a true blocked algorithm (that casts most computation in terms of matrix-matrix multiplication). The following papers are related to this:

  • [33] Gregorio Quintana-Orti, Xioabai Sun, and Christof H. Bischof, A BLAS-3 version of the QR factorization with column pivoting, SIAM Journal on Scientific Computing, 19, 1998.

    discusses how too cast approximately half the computation in terms of matrix-matrix multiplication.

  • [25] Per-Gunnar Martinsson, Gregorio Quintana-Orti, Nathan Heavner, Robert van de Geijn, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), SIAM Journal on Scientific Computing, Vol. 39, Issue 2, 2017.

    shows how a randomized algorithm can be used to cast most computation in terms of matrix-matrix multiplication.

login