rocsolver_scholqr Interface Reference

rocsolver_scholqr Interface Reference#

hipFORT API Reference: hipfort_rocsolver::rocsolver_scholqr Interface Reference

CHOLQR computes an orthogonal factorization of a number of columns (rows) of a general m-by-n matrix \(A\) using the Cholesky factorization of \(A'A\) if \(m ≥ n\) or \(AA'\) if \(m < n\). More...

Public Member Functions
integer(c_int) function	rocsolver_scholqr_ (handle, cholshift, cholnum, m, n, a, lda, w, ldw, sigma, nr)

Detailed Description

CHOLQR computes an orthogonal factorization of a number of columns (rows) of a general m-by-n matrix \(A\) using the Cholesky factorization of \(A'A\) if \(m ≥ n\) or \(AA'\) if \(m < n\).

The factorization has the form

\[ A = H W, \quad \text{with} \]

\[ H = \left[\begin{array}{c|c} Q & A^* \end{array}\right], \quad \text{and} \quad W = \left[\begin{array}{c|c} R & 0\\% \hline 0 & I_{n-\text{nr}} \end{array}\right] \]

if \(m ≥ n\), or

\[ A = W H, \quad \text{with} \]

\[ H = \left[\begin{array}{c} Q \\% A^* \end{array}\right], \quad \text{and} \quad W = \left[\begin{array}{c|c} L & 0\\% \hline 0 & I_{m-\text{nr}} \end{array}\right] \]

if \(m < n\).

R is an nr-by-nr upper triangular matrix. L is an nr-by-nr lower triangular matrix. Q is an m-by-nr (or nr-by-n) matrix with orthonormal columns (rows), and matrix A* represents the last n - nr columns (or m - nr rows) of A. nr is an output argument that indicates the number of columns (rows) of A that were properly factorized by the function ( \(\text{nr} ≤ \text{min}(m,n)\)). The factorization is computed using the CholeskyQR algorithm as described below.

The algorithm starts by computing \(B = A'A\) (or \(B = AA'\)), and produces \(W\) via the Cholesky factorization \(B=W'W\) (or \(B=WW'\)). Finally, it computes the factor \(H\) as the solution of the triangular system \(A=HW\) ( \(A=WH\)).

The initial Cholesky factorization could fail if B is not positive definite, which could happen when A is ill-conditioned or singular. In this case, only nr columns (rows) of B will be reduced properly, which yields the general form of the factor W depicted above. nr is thus related with the value of info as returned by POTRF.

Alternatively, the algorithm could use a preconditioned matrix \(B = A'A + \text{sigma}\cdot I\) (or \(B = AA' + \text{sigma}\cdot I\)) to increase the chances of the Cholesky factorization of B to succeed, and thus increasing the value of nr. The shift, sigma, could be provided by the user (if cholshift = rocsolver_cholqr_shift_provided), or an "ideal" number could be computed internally (if cholshift = rocsolver_cholqr_shift_computed). If cholshift = rocsolver_cholqr_shift_none, then sigma is not referenced and could be null.

Additionally, an iterative refinement process could be used to improve the orthonormality of the columns (or rows) in Q. If \(A=Q_1R_1\) (or \(A=L_1Q_1\)) is an initial factorization of A, one can always re-apply the CholeskyQR process to \(Q_1\) to produce \(Q_1=Q_2R_2\) (or \(Q_1=L_2Q_2\)). This would yield a new factorization \(A=QR\) (or \(A=LQ\)), with \(R=R_2R_1\) ( \(L=L_1L_2\)), and \(Q=Q_2\). The columns (rows) of Q are now expected to be closer to be orthonormal than the columns (rows) of the initial \(Q_1\). CHOLQR will execute cholnum - 1 extra Cholesky factorizations to refine the factor Q.

Note

If the Cholesky factorization of B fails, it returns the order of the first leading minor of B that is negative or zero as the value in info. nr is then equal to info

1. However, the Cholesky factorization is not inherently a rank revealing method. Thus, nr should not be interpreted as the numerical rank of matrix A.

Common configurations of the CholeskyQR algorithm studied in the literature include: CholeskyQR1, which is equivalent to cholshift = rocsolver_cholqr_shift_none, and cholnum = 1; CholeskyQR2, equivalent to cholshift = rocsolver_cholqr_shift_none, and cholnum = 2; and ShiftedCholeskyQR3, which can be executed with cholshift = rocsolver_cholqr_shift_computed, and cholnum = 3. It is documented that ShiftedCholeskyQR3 can successfully factorize ill-conditioned matrices with condition numbers up to \(O(\text{eps}^{-1})\) (i.e. \(\approx 4\times10^{15}\) in double precision).

Even if the factorization is complete, i.e. nr = min(m,n), the returned factors H and W do not form a full QR (or LQ) factorization of A. H will always be missing the last columns (rows) which correspond to the m - n (or n - m) orthonormal vectors generating the row (column) null-space of A. In other words, cholqr cannot be used as a row (column) compression method if the back transformation is required.

Parameters

[in]	handle	- rocblas_handle.
[in]	cholshift	- `rocsolver_cholqr_shift`. Specifies how the shift sigma will be used in the Cholesky factorization.
[in]	cholnum	- rocblas_int. cholnum > 0 if cholshift = rocsolver_cholqr_shift_none, cholnum > 1 otherwise. Specifies how many Cholesky factorizations will be executed in total. cholnum - 1 factorization will be used for the refinement of Q.
[in]	m	- rocblas_int. m >= 0. The number of rows of the matrix A.
[in]	n	- rocblas_int. n >= 0. The number of columns of the matrix A.
[in,out]	A	- pointer to type. Array on the GPU of dimension lda*n. On entry, the m-by-n matrix to be factored. On exit, it is overwritten by the factor H.
[in]	lda	- rocblas_int. lda >= m. Specifies the leading dimension of A.
[out]	W	- pointer to type. Array on the GPU of dimension ldw*min(m,n). The min(m,n)-by-min(m,n) upper (lower) triangular factor W.
[in]	ldw	- rocblas_int. ldw >= min(m,n). Specifies the leading dimension of W.
[in,out]	sigma	- pointer to real type on the GPU. For rocsolver_cholqr_shift_computed: On exit, contains the computed shift value. For rocsolver_cholqr_shift_provided: On entry, contains the user-provided shift value. Not referenced for rocsolver_cholqr_shift_none.
[out]	nr	- pointer to rocblas_int on the GPU. The number of columns (rows) of A succesfully factorized.

Member Function/Subroutine Documentation