Singular Value Decomposition (SVD) for Bidiagonal Matrices#

Background#

BDSVD (BiDiagonal Singular Value Decomposition) computes the singular values and, optionally, the left and/or right singular vectors of batched bidiagonal matrices using the QR algorithm.

\[A = U \Sigma V^H\]

where:

  • \(A\) is an \(M \times M\) bidiagonal matrix,

  • \(\Sigma\) is an \(M \times M\) diagonal matrix containing the singular values of \(A\) in descending order (singular values are always real and non-negative),

  • \(U\) is an \(M \times M\) unitary matrix containing the left singular vectors of \(A\), and

  • \(V^H\) is an \(M \times M\) unitary matrix representing the conjugate transpose of \(V\), containing the right singular vectors of \(A\).

Device API#

The cuSolverDx bdsvd device functions are as follows (see Execution Methods):

// Compute singular values only
__device__ void execute(data_type* d, data_type* e, status_type* info);

// Compute singular values and the right/left singular vectors
__device__ void execute(data_type* d, data_type* e, data_type* U, data_type* VH, status_type* info);
// Compute singular values and the right/left singular vectors with runtime leading dimensions of U and VH
__device__ void execute(data_type* d, data_type* e, data_type* U, const unsigned int ldu,
                        data_type* VH, const unsigned int ldvt, status_type* info);

Parameters:

  • d: Diagonal elements of the bidiagonal matrix A (size M per batch). On exit, contains the singular values in descending order.

  • e: Off-diagonal elements of the bidiagonal matrix A (size M-1 per batch). On exit, this array is destroyed.

  • U: Batched left singular vectors matrix (size \(M \times M\) per batch).

  • VH: Batched right singular vectors matrix (\(V^H\), size \(M \times M\) per batch).

  • info: Status code for each batch (see Return Status).

Note

The bdsvd function returns \(V^H\) rather than \(V\) itself, consistent with standard LAPACK conventions.

Important

cuSolverDx bdsvd only supports upper bidiagonal matrices. For lower bidiagonal matrices, use the property \(A^H = V \Sigma U^H\).

Important

cuSolverDx bdsvd only supports real data types for matrix A, its singular values, and singular vectors.

Job Options#

The Job operator controls whether singular vectors are computed and how they are stored. If singular vectors are requested, matrices \(U\) and \(VH\) of size \(M \times M\) are required as input, with leading dimensions \(\mathrm{ldu} \geq M\) and \(\mathrm{ldvt} \geq M\).

Left singular vectors (jobu):

  • job::no_vectors: U is ignored; no left singular vectors are computed.

  • job::all_vectors or job::some_vectors: The function computes the left singular vectors of A and returns the result in U.

  • job::multiply_vectors: The function computes the left singular vectors of A, multiplies them with input_U on the right, i.e., input_U * computed_U, and overwrites U with the result.

Right singular vectors (jobvt):

  • job::no_vectors: VH is ignored; no right singular vectors are computed.

  • job::all_vectors or job::some_vectors: The function computes the right singular vectors of A and returns the result in VH.

  • job::multiply_vectors: The function computes the right singular vectors of A, multiplies them with input_VH on the left, i.e., computed_VH * input_VH, and overwrites VH with the result.

Note

For bdsvd, job::all_vectors and job::some_vectors are equivalent because the bidiagonal matrix is always square. In contrast, for gesvd they differ based on the matrix dimensions.

Return Status#

The function returns a status code info for each batch:

  • info = 0: The function completed successfully.

  • info > 0: The algorithm did not converge within 30 * M iterations; specifically, info elements of e have not converged to zero.

Supported Configurations#

  1. Arrangement: U and VH can independently use column-major or row-major layouts. Use the Arrangement<Urr, VHrr> operator, where Urr and VHrr specify the layouts for U and VH respectively (see Arrangement operator).

  2. Leading Dimensions: Leading dimensions for U and VH can be set independently using the LeadingDimension<LDU, LDVH> operator (see LeadingDimension operator).

  3. Job Options: The Job operator accepts job::no_vectors, job::all_vectors, job::some_vectors, or job::multiply_vectors for left and right singular vectors (see Job operator):

    • job::overwrite_vectors is not supported for bdsvd; using it results in a compile-time error.

    • If job::no_vectors is selected and U/VH pointers are provided, they are ignored.

    • If job::no_vectors is selected, any leading dimension or arrangement specified is ignored.

Warning

Unlike LAPACK’s bdsqr, cuSolverDx bdsvd functions only guarantee that computed singular values are accurate to \(O(u||A||_2)\), where \(u\) is the unit-roundoff error for the precision.