NAG FL Interface
g13ebf (multi_​kalman_​sqrt_​invar)

Settings help

FL Name Style:


FL Specification Language:


1 Purpose

g13ebf performs a combined measurement and time update of one iteration of the time-invariant Kalman filter using a square root covariance filter.

2 Specification

Fortran Interface
Subroutine g13ebf ( transf, n, m, l, a, lds, b, stq, q, ldq, c, ldm, r, s, k, h, u, tol, iwk, wk, ifail)
Integer, Intent (In) :: n, m, l, lds, ldq, ldm
Integer, Intent (Inout) :: ifail
Integer, Intent (Out) :: iwk(m)
Real (Kind=nag_wp), Intent (In) :: q(ldq,*), r(ldm,m), tol
Real (Kind=nag_wp), Intent (Inout) :: a(lds,n), b(lds,l), c(ldm,n), s(lds,n), k(lds,m), h(ldm,m), u(lds,*)
Real (Kind=nag_wp), Intent (Out) :: wk((n+m)*(n+m+l))
Logical, Intent (In) :: stq
Character (1), Intent (In) :: transf
C Header Interface
#include <nag.h>
void  g13ebf_ (const char *transf, const Integer *n, const Integer *m, const Integer *l, double a[], const Integer *lds, double b[], const logical *stq, const double q[], const Integer *ldq, double c[], const Integer *ldm, const double r[], double s[], double k[], double h[], double u[], const double *tol, Integer iwk[], double wk[], Integer *ifail, const Charlen length_transf)
The routine may be called by the names g13ebf or nagf_tsa_multi_kalman_sqrt_invar.

3 Description

The Kalman filter arises from the state space model given by
Xi+1=AXi+BWi, Var(Wi)=Qi Yi=CXi+Vi, Var(Vi)=Ri  
where Xi is the state vector of length n at time i, Yi is the observation vector of length m at time i and Wi of length l and Vi of length m are the independent state noise and measurement noise respectively. The matrices A,B and C are time invariant.
The estimate of Xi given observations Y1 to Yi-1 is denoted by X^ii-1 with state covariance matrix Var(X^ii-1)=Pii-1=SiSiT while the estimate of Xi given observations Y1 to Yi is denoted by X^ii with covariance matrix Var(X^ii)=Pii. The update of the estimate, X^ii-1, from time i to time (i+1) is computed in two stages. First, the measurement-update is given by
X^ii=X^ii-1+Ki[Yi-CX^ii-1] (1)
where Ki=PiiCT[CPiiCT+Ri] −1 is the Kalman gain matrix. The second stage is the time-update for X, which is given by
X^i+1i=AX^ii+DiUi (2)
where DiUi represents any deterministic control used.
The square root covariance filter algorithm provides a stable method for computing the Kalman gain matrix and the state covariance matrix. The algorithm can be summarised as
( Ri1/2 0 CSi 0 BQi1/2 ASi ) U=( Hi1/2 0 0 Gi Si+1 0 )  
where U is an orthogonal transformation triangularizing the left-hand pre-array to produce the right-hand post-array. The triangularization is carried out via Householder transformations exploiting the zero pattern of the pre-array. The relationship between the Kalman gain matrix Ki and Gi is given by
AKi=Gi (Hi1/2) −1.  
In order to exploit the invariant parts of the model to simplify the computation of U the results for the transformed state space U*X are computed where U* is the transformation that reduces the matrix pair (A,C) to lower observer Hessenberg form. That is, the matrix U* is computed such that the compound matrix
[ CU*T U*AU*T ]  
is a lower trapezoidal matrix. Further the matrix B is transformed to U*B. These transformations need only be computed once at the start of a series, and g13ebf will, optionally, compute them. g13ebf returns transformed matrices U*AU*T, U*B, CU*T and U*AKi, the Cholesky factor of the updated transformed state covariance matrix Si+1* (where U*Pi+1iU*T=Si+1*Si+1 *T) and the matrix Hi1/2, valid for both transformed and original models, which is used in the computation of the likelihood for the model. Note that the covariance matrices Qi and Ri can be time-varying.

4 References

Vanbegin M, van Dooren P and Verhaegen M H G (1989) Algorithm 675: FORTRAN subroutines for computing the square root covariance filter and square root information filter in dense or Hessenberg forms ACM Trans. Math. Software 15 243–256
Verhaegen M H G and van Dooren P (1986) Numerical aspects of different Kalman filter implementations IEEE Trans. Auto. Contr. AC-31 907–917

5 Arguments

1: transf Character(1) Input
On entry: indicates whether to transform the input matrix pair (A,C) to lower observer Hessenberg form. The transformation will only be required on the first call to g13ebf.
transf='T'
The matrices in arrays a and c are transformed to lower observer Hessenberg form and the matrices in b and s are transformed as described in Section 3.
transf='H'
The matrices in arrays a, c and b should be as returned from a previous call to g13ebf with transf='T'.
Constraint: transf='T' or 'H'.
2: n Integer Input
On entry: n, the size of the state vector.
Constraint: n1.
3: m Integer Input
On entry: m, the size of the observation vector.
Constraint: m1.
4: l Integer Input
On entry: l, the dimension of the state noise.
Constraint: l1.
5: a(lds,n) Real (Kind=nag_wp) array Input/Output
On entry: if transf='T', the state transition matrix, A.
If transf='H', the transformed matrix as returned by a previous call to g13ebf with transf='T'.
On exit: if transf='T', the transformed matrix, U*AU*T, otherwise a is unchanged.
6: lds Integer Input
On entry: the first dimension of the arrays a, b, s, k and u as declared in the (sub)program from which g13ebf is called.
Constraint: ldsn.
7: b(lds,l) Real (Kind=nag_wp) array Input/Output
On entry: if transf='T', the noise coefficient matrix B.
If transf='H', the transformed matrix as returned by a previous call to g13ebf with transf='T'.
On exit: if transf='T', the transformed matrix, U*B, otherwise b is unchanged.
8: stq Logical Input
On entry: if stq=.TRUE., the state noise covariance matrix Qi is assumed to be the identity matrix. Otherwise the lower triangular Cholesky factor, Qi1/2, must be provided in q.
9: q(ldq,*) Real (Kind=nag_wp) array Input
Note: the second dimension of the array q must be at least l if stq=.FALSE..
On entry: if stq=.FALSE., q must contain the lower triangular Cholesky factor of the state noise covariance matrix, Qi1/2. Otherwise q is not referenced.
10: ldq Integer Input
On entry: the first dimension of the array q as declared in the (sub)program from which g13ebf is called.
Constraints:
  • if stq=.FALSE., ldql;
  • otherwise ldq1.
11: c(ldm,n) Real (Kind=nag_wp) array Input/Output
On entry: if transf='T', the measurement coefficient matrix, C.
If transf='H', the transformed matrix as returned by a previous call to g13ebf with transf='T'.
On exit: if transf='T', the transformed matrix, CU*T, otherwise c is unchanged.
12: ldm Integer Input
On entry: the first dimension of the arrays c, r and h as declared in the (sub)program from which g13ebf is called.
Constraint: ldmm.
13: r(ldm,m) Real (Kind=nag_wp) array Input
On entry: the lower triangular Cholesky factor of the measurement noise covariance matrix Ri1/2.
14: s(lds,n) Real (Kind=nag_wp) array Input/Output
On entry: if transf='T' the lower triangular Cholesky factor of the state covariance matrix, Si.
If transf='H' the lower triangular Cholesky factor of the covariance matrix of the transformed state vector Si* as returned from a previous call to g13ebf with transf='T'.
On exit: the lower triangular Cholesky factor of the transformed state covariance matrix, Si+1*.
15: k(lds,m) Real (Kind=nag_wp) array Output
On exit: the Kalman gain matrix for the transformed state vector premultiplied by the state transformed transition matrix, U*AKi.
16: h(ldm,m) Real (Kind=nag_wp) array Output
On exit: the lower triangular matrix Hi1/2.
17: u(lds,*) Real (Kind=nag_wp) array Output
Note: the second dimension of the array u must be at least n if transf='T'.
On exit: if transf='T' the n×n transformation matrix U*, otherwise u is not referenced.
18: tol Real (Kind=nag_wp) Input
On entry: the tolerance used to test for the singularity of Hi1/2. If 0.0tol<m2×machine precision, then m2×machine precision is used instead. The inverse of the condition number of H1/2 is estimated by a call to f07tgf. If this estimate is less than tol then H1/2 is assumed to be singular.
Suggested value: tol=0.0.
Constraint: tol0.0.
19: iwk(m) Integer array Workspace
20: wk((n+m)×(n+m+l)) Real (Kind=nag_wp) array Workspace
21: ifail Integer Input/Output
On entry: ifail must be set to 0, −1 or 1 to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of 0 causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of −1 means that an error message is printed while a value of 1 means that it is not.
If halting is not appropriate, the value −1 or 1 is recommended. If message printing is undesirable, then the value 1 is recommended. Otherwise, the value 0 is recommended. When the value -1 or 1 is used it is essential to test the value of ifail on exit.
On exit: ifail=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry ifail=0 or −1, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
ifail=1
On entry, l=value.
Constraint: l1.
On entry, ldm=value and m=value.
Constraint: ldmm.
On entry, ldq=value.
Constraint: ldq1.
On entry, ldq=value and l=value.
Constraint: ldql.
On entry, lds=value and n=value.
Constraint: ldsn.
On entry, m=value.
Constraint: m1.
On entry, n=value.
Constraint: n1.
On entry, tol=value.
Constraint: tol0.0.
On entry, transf=value.
Constraint: transf='T' or 'H'.
ifail=2
The matrix Hi1/2 is singular.
ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
ifail=-399
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
ifail=-999
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

The use of the square root algorithm improves the stability of the computations as compared with the direct coding of the Kalman filter. The accuracy will depend on the model.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.
g13ebf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
g13ebf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

For models with time-varying A,B and C, g13eaf can be used.
The initial estimate of the transformed state vector can be computed from the estimate of the original state vector X^10, say, by premultiplying it by U* as returned by g13ebf with transf='T'; that is, X^10*=U*X^10. The estimate of the transformed state vector X^i+1i* can be computed from the previous value X^ii-1* by
X^i+1i*=(U*AU*T)X^ii-1*+(U*AKi)ri  
where
ri=Yi-(CU*T)X^ii- 1*  
are the independent one-step prediction residuals for both the transformed and original model. The estimate of the original state vector can be computed from the transformed state vector as U*TX^1+1i*. The required matrix-vector multiplications can be performed by f06paf.
If Wi and Vi are independent multivariate Normal variates then the log-likelihood for observations i=1,2,,t is given by
l(θ) = κ - 12 i=1 t l n (det(Hi)) - 12 i=1 t (Yi-CiXii-1) T Hi-1 (Yi-Ci X ii-1 )  
where κ is a constant.
The Cholesky factors of the covariance matrices can be computed using f07fdf.
Note that the model
Xi+1=AXi+Wi, Var(Wi)=Qi Yi=CXi+Vi, Var(Vi)=Ri  
can be specified either with b set to the identity matrix and stq=.FALSE. and the matrix Q1/2 input in q or with stq=.TRUE. and b set to Q1/2.
The algorithm requires 16n3+n2(32m+l)+2nm2+23p3 operations and is backward stable (see Verhaegen and van Dooren (1986)). The transformation to lower observer Hessenberg form requires O((n+m)n2) operations.

10 Example

This example first inputs the number of updates to be computed and the problem sizes. The initial state vector and the Cholesky factor of the state covariance matrix are input followed by the model matrices A,B,C,R1/2 and optionally Q1/2 (the Cholesky factors of the covariance matrices being input). At the first update the matrices are transformed using the transf='T' option and the initial value of the state vector is transformed. At each update the observed values are input and the residuals are computed and printed and the estimate of the transformed state vector, U^*Xii-1, and the deviance are updated. The deviance is −2×log-likelihood ignoring the constant. After the final update the estimate of the state vector is computed from the transformed state vector and the state covariance matrix is computed from s and these are printed along with the value of the deviance.
The data is for a two-dimensional time series to which a VARMA(1,1) has been fitted. For the specification of a VARMA model as a state space model see the G13 Chapter Introduction. The means of the two series are included as additional states that do not change over time. The initial value of P, P0, is the solution to
P0=AP0AT+BQBT.  

10.1 Program Text

Program Text (g13ebfe.f90)

10.2 Program Data

Program Data (g13ebfe.d)

10.3 Program Results

Program Results (g13ebfe.r)