warp.tile_ldlt#
- warp.tile_ldlt( ) tuple[Tile[Float, tuple[int, int]], Tile[int32, tuple[int]], Tile[int32, tuple[int]]]#
Compute a Bunch-Kaufman factorization of a real symmetric square tile.
Factor the symmetric matrix defined by the selected triangle of
Awithout modifyingA; the other triangle is ignored. This is a cooperative operation, so every thread in the block must call it.Automatic differentiation of the packed factors holds the recorded permutation and diagonal-block choices fixed. Pivot indices and status are nondifferentiable. Gradients are undefined for singular inputs or at boundaries where the pivot or block choices change. Only the selected input triangle receives gradients; each off-diagonal input represents both symmetric matrix entries. On CUDA, a kernel compiled with backward support reserves additional static shared memory for the adjoint, which can limit the tile size. See Shared Memory Budget for how to budget shared memory and for forward-only options.
- Parameters:
A – A nonempty real tile with
shape=(N, N)and dtypefloat32orfloat64, with finite entries in the selected triangle.fill_mode – Compile-time triangle selector,
"lower"or"upper".
- Returns:
ld: The packed factors, withshape=(N, N)and the dtype ofA. Forfill_mode="lower", they satisfyP @ A @ P.T = L @ D @ L.T, whereLis unit lower triangular andDis symmetric block diagonal with 1-by-1 and 2-by-2 blocks. The diagonal ofldholds the diagonal ofD. For each 2-by-2 block starting atk,ld[k+1, k]holds its off-diagonal entry, andL[k+1, k]is zero. All other strict lower entries holdL, which is already in permuted row order, so it needs no further row swaps. The upper triangle ofldis zero. Forfill_mode="upper", the storage is transposed:ldholdsU = L.Tand the upper triangle ofD, satisfyingP @ A @ P.T = U.T @ D @ U, and the lower triangle is zero.pivots: Anint32tile withshape=(N,)that encodes the symmetric swaps and block sizes for either fill mode. Decode it in increasing index order. Ifpivots[k] >= 0, interchange rows and columnskandpivots[k]and advance by one, which denotes a 1-by-1 diagonal block. Otherwise,pivots[k] == pivots[k+1] == -(p+1)denotes a 2-by-2 block: interchange rows and columnsk+1andp, then advance by two. Apply the swaps to an identity permutation to constructP.info: Anint32tile withshape=(1,). Zero indicates success. A positive valueiidentifies the first exactly zero 1-by-1 pivotD[i-1, i-1]. Factorization completes for singular inputs, but the factors cannot then be used for a nonsingular solve. This status does not estimate conditioning.
- Return type:
A tuple
(ld, pivots, info)of tiles with dense shared storage
Example
Factor a KKT matrix and check its inertia from the diagonal of
D. For this matrix every pivot is 1-by-1, soPfollows from the swaps directly.@wp.kernel def factor_kernel( a: wp.array2d[float], factors: wp.array2d[float], pivots: wp.array[int], status: wp.array[int], ): ld, p, info = wp.tile_ldlt(wp.tile_load(a, shape=(4, 4))) wp.tile_store(factors, ld) wp.tile_store(pivots, p) wp.tile_store(status, info) # [[0, C], [C.T, H]] with two constraints and two primal variables a_np = np.array( [[0.0, 0.0, 1.0, 0.0], [0.0, 0.0, 0.0, 1.0], [1.0, 0.0, 4.0, 1.0], [0.0, 1.0, 1.0, 3.0]], dtype=np.float32, ) a = wp.array(a_np) factors = wp.zeros((4, 4), dtype=float) pivots = wp.zeros(4, dtype=int) status = wp.zeros(1, dtype=int) # one full warp cooperates on the factorization wp.launch_tiled(factor_kernel, dim=1, inputs=[a], outputs=[factors, pivots, status], block_dim=32) ld = factors.numpy() swaps = pivots.numpy() perm = np.arange(4) for k in range(4): # all pivots are 1-by-1 here perm[[k, swaps[k]]] = perm[[swaps[k], k]] ell = np.tril(ld, -1) + np.eye(4) reconstructed = ell @ np.diag(np.diag(ld)) @ ell.T print(status.numpy()[0], np.allclose(reconstructed, a_np[np.ix_(perm, perm)], atol=1e-5)) print((np.diag(ld) > 0).sum(), (np.diag(ld) < 0).sum())
0 True 2 2