Index-> contents reference index search external Previous Next Up-> ckbs utility ckbs_tridiag_solve ckbs-> license ckbs_t_general ckbs_nonlinear ckbs_L1_nonlinear ckbs_affine ckbs_affine_singular ckbs_L1_affine utility all_ok.m whatsnew wishlist bib utility-> ckbs_t_obj ckbs_t_grad ckbs_t_hess ckbs_diag_solve ckbs_bidiag_solve ckbs_bidiag_solve_t ckbs_blkbidiag_symm_mul ckbs_blkdiag_mul ckbs_blkdiag_mul_t ckbs_blkbidiag_mul_t ckbs_blkbidiag_mul ckbs_blktridiag_mul ckbs_sumsq_obj ckbs_L2L1_obj ckbs_sumsq_grad ckbs_process_grad ckbs_sumsq_hes ckbs_process_hes ckbs_tridiag_solve ckbs_tridiag_solve_b ckbs_tridiag_solve_pcg ckbs_newton_step ckbs_newton_step_L1 ckbs_kuhn_tucker ckbs_kuhn_tucker_L1 ckbs_tridiag_solve-> tridiag_solve_ok.m Headings-> Syntax Purpose b c r e lambda Reference Lemma Example

Symmetric Block Tridiagonal Algorithm

Syntax
[e, lambda] = ckbs_tridiag_solve(b, c, r)

Purpose
This routine solves the following linear system of equations for   e :   $A * e = r$  where the symmetric block tridiagonal matrix   A is defined by   $A = \left( \begin{array}{ccccc} b_1 & c_2^\R{T} & 0 & \cdots & 0 \\ c_2 & b_2 & c_3^\R{T} & & \vdots \\ \vdots & & \ddots & & \\ 0 & \cdots & & b_N & c_N \end{array} \right)$  The routine ckbs_tridiag_solve_b solves the same problem. The difference is that this routine runs the reduction starting at the first block rather than the last block of the matrix, which is less stable for this application.

b
The argument b is a three dimensional array, for   k = 1 , \ldots , N   $b_k = b(:,:,k)$ and b has size   n \times n \times N .

c
The argument c is a three dimensional array, for   k = 2 , \ldots , N   $c_k = c(:,:,k)$ and c has size   n \times n \times N .

r
The argument r is an   (n * N) \times m matrix.

e
The result e is an   (n * N) \times m matrix.

lambda
The result lambda is a scalar equal to the logarithm of the determinant of   A .

Reference
The marginal likelihood for parameters in a discrete Gauss Markov process , Bradley M. Bell, IEEE Transactions on Signal Processing, Vol. 48, No. 3, March 2000.

Lemma
The following result is proven as Lemma 6 of the reference above: Suppose that for   k = 1 , \ldots , N   $\begin{array}{rcl} b_k & = & u_k + q_{k-1}^{-1} + a_k * q_k^{-1} * a_k^\R{T} \\ c_k & = & q_{k-1}^{-1} * a_k^\R{T} \end{array}$  where   u_k is symmetric positive semi-definite and   q_k is symmetric positive definite. It follows that the algorithm used by ckbs_tridiag_solve is well conditioned and will not try to invert singular matrices.

Example
The file tridiag_solve_ok.m contains an example and test of ckbs_tridiag_solve. It returns true if ckbs_tridiag_solve passes the test and false otherwise.
Input File: src/ckbs_tridiag_solve.m