Is it possible tp parallelize Kalman Filter?

This is for a course project. I have a kalman filter code posted below, and i need to write code in Paralllel Computing toolbox so that it can be executed in several processes. Do you guys think it's possible to parallelize Kalman Filter? thank you very much!

%%%%%%%%%%%%%%%%%%%Kalman filter%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% run Kalman filter
    xfilt = zeros( k, T);
    Vfilt = zeros( k, k, T);
    Vmfilt = zeros( k, k, T);

      Z = data;

    %%%%%%%%%%%Initialize log-likelihood%%%%%%%%
      loglik = 0;

              for i=1:T
                  % Predict
                  if i==1
                      xhatm = F*x0;
                      Vm = F*V0*F' + Q;
                  else
                      xhatm = F*xhat;
                      Vm = F*V*F' + Q;
                  end

                  % Update
                  S = H*Vm*H' + R;% the covariance matrix of Y estimation and Y real-value.
                  K = Vm * H' / S;
                  xhat = xhatm + K*( Z(:,i) - H*xhatm );%equation (4.39) 
                  V = ( eye(k) - K*H) * Vm;

                  xfilt(:,i) = xhat; %save xhat to Vfilt matrix
                  Vfilt(:,:,i) = V; %save V to Vfilt matrix
                  Vmfilt(:,:,i) = Vm; %save Vm to Vmfilt matrix,

                  % Update log likelihood
                  loglik = loglik - (n/2)*log(2*pi) - .5 * log( abs(det(S)) ) -.5*(( Z(:,i) - H*xhatm )' / S)*( Z(:,i) - H*xhatm );
              end %det: determinant of matrix S.

      loglik_array(num_iter) = loglik;

Answer 1

[Friedrich]

Hi,

no that is not possible since the way the Kalman Filter is used shows that the itterations are not independent of each other. So you can't do the calculation for i = 5 before you have done i = 4 and so on. Which means you can't run it in parallel.

You can obtain that dependency when looking at the underlying model ( http://en.wikipedia.org/wiki/Kalman_filter )

x_k = F_k * x_{k-1} + B_k * u_k + w_k

There you can see an x_{k-1} which shows again that you need to calculate the Kalman Filter sequentially.

[Andrew]

thank you very much for your reply!

yes, you are right. It's not possible to parallelize the "for" iterations.

Now I m wondering if the matrix multiply in the equations can be performed by several processors. Like this one introduces:

http://www.cs.indiana.edu/classes/b673/notes/matrix_mult.html