rocsolver_scholqr_batched Interface Reference

rocsolver_scholqr_batched Interface Reference#

hipFORT API Reference: hipfort_rocsolver::rocsolver_scholqr_batched Interface Reference

CHOLQR_BATCHED computes an orthogonal factorization of a number of columns (rows) of a batch of general m-by-n matrices \(A_l\) using the Cholesky factorization of \(A_l'A_l\) if \(m ≥ n\) or \(A_lA_l'\) if \(m < n\). More...

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

Detailed Description

CHOLQR_BATCHED computes an orthogonal factorization of a number of columns (rows) of a batch of general m-by-n matrices \(A_l\) using the Cholesky factorization of \(A_l'A_l\) if \(m ≥ n\) or \(A_lA_l'\) if \(m < n\).

For each instance of the batch, the factorization has the form

\[ A_l = H_l W_l, \quad \text{with} \]

\[ H_l = \left[\begin{array}{c|c} Q_l & A_l^* \end{array}\right], \quad \text{and} \quad W_l = \left[\begin{array}{c|c} R_l & 0\\% \hline 0 & I_{n-\text{nr[l]}} \end{array}\right] \]

if \(m ≥ n\), or

\[ A_l = W_l H_l, \quad \text{with} \]

\[ H_l = \left[\begin{array}{c} Q_l \\% A_l^* \end{array}\right], \quad \text{and} \quad W_l = \left[\begin{array}{c|c} L_l & 0\\% \hline 0 & I_{m-\text{nr[l]}} \end{array}\right] \]

if \(m < n\).

\(R_l\) is an nr[l]-by-nr[l] upper triangular matrix. \(L_l\) is an nr[l]-by-nr[l] lower triangular matrix. \(Q_l\) is an m-by-nr[l] (or nr[l]-by-n) matrix with orthonormal columns (rows), and matrix \(A_l^*\) represents the last n - nr[l] columns (or m - nr[l] rows) of \(A_l\). nr[l], the l-th element of vector nr, is an output argument that indicates the number of columns (rows) of \(A_l\) that were properly factorized by the function ( \(\text{nr[l]} ≤ \text{min}(m,n)\)). The factorization is computed using the CholeskyQR algorithm as described below.

The algorithm starts by computing \(B_l = A_l'A_l\) (or \(B_l = A_lA_l'\)), and produces \(W_l\) via the Cholesky factorization \(B_l=W_l'W_l\) (or \(B_l=W_lW_l'\)). Finally, it computes the factor \(H_l\) as the solution of the triangular system \(A_l=H_lW_l\) ( \(A_l=W_lH_l\)).

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

Alternatively, the algorithm could use a preconditioned matrix \(B_l = A_l'A_l + \text{sigma[l]}\cdot I\) (or \(B_l = A_lA_l' + \text{sigma[l]}\cdot I\)) to increase the chances of the Cholesky factorization of \(B_l\) to succeed, and thus increasing the value of nr[l]. The shift, sigma[l], 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_l\). If \(A_l=Q_{l_1}R_{l_1}\) (or \(A_l=L_{l_1}Q_{l_1}\)) is an initial factorization of \(A_l\), one can always re-apply the CholeskyQR process to \(Q_{l_1}\) to produce \(Q_{l_1}=Q_{l_2}R_{l_2}\) (or \(Q_{l_1}=L_{l_2}Q_{l_2}\)). This would yield a new factorization \(A_l=Q_lR_l\) (or \(A_l=L_lQ_l\)), with \(R_l=R_{l_2}R_{l_1}\) ( \(L_l=L_{l_1}L_{l_2}\)), and \(Q_l=Q_{l_2}\). The columns (rows) of \(Q_l\) are now expected to be closer to be orthonormal than the columns (rows) of the initial \(Q_{l_1}\). CHOLQR will execute cholnum - 1 extra Cholesky factorizations to refine the factor \(Q_l\).

Note: If the Cholesky factorization of \(B_l\) fails, it returns the order of the first leading minor of \(B_l\) that is negative or zero as the value in info[l]. nr[l] is then equal to info[l] - 1. However, the Cholesky factorization is not inherently a rank revealing method. Thus, nr[l] should not be interpreted as the numerical rank of matrix \(A_l\).; 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 of a matrix in the batch is complete, i.e. nr[l] = min(m,n), the returned factors \(H_l\) and \(W_l\) do not form a full QR (or LQ) factorization of \(A_l\). \(H_l\) 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_l\). 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_l.
[in]	m	- rocblas_int. m >= 0. The number of rows of the matrices A_l.
[in]	n	- rocblas_int. n >= 0. The number of columns of the matrices A_l.
[in,out]	A	- Array of pointers to type. Each pointer points to an array on the GPU of dimension lda*n. On entry, the m-by-n matrices A_l to be factored. On exit, it is overwritten by the factors H_l.
[in]	lda	- rocblas_int. lda >= m. Specifies the leading dimension of A_l.
[out]	W	- pointer to type. Array on the GPU (the size depends on the value of strideW). The min(m,n)-by-min(m,n) upper (lower) triangular factors W_l.
[in]	ldw	- rocblas_int. ldw >= min(m,n). Specifies the leading dimension of W_l.
[in]	strideW	- rocblas_stride. Stride from the start of one matrix W_l to the next one W_(l+1). There is no restriction for the value of strideW. Normal use case is strideW >= ldw*min(m,n).
[in,out]	sigma	- pointer to real type. Array on the GPU of size batch_count. For rocsolver_cholqr_shift_computed: On exit, contains the computed shift values. For rocsolver_cholqr_shift_provided: On entry, contains the user-provided shift values. Not referenced for rocsolver_cholqr_shift_none.
[out]	nr	- pointer to rocblas_int. Array on the GPU of size batch_count. The number of columns (rows) succesfully factorized of each A_l.
[in]	batch_count	- rocblas_int. batch_count >= 0. Number of matrices in the batch.

Member Function/Subroutine Documentation