Editing Kalman filter (section)

== Parallel form ==
The Kalman filter is efficient for sequential data processing on [[central processing units]] (CPUs), but in its original form it is inefficient on parallel architectures such as [[graphics processing units]] (GPUs). It is however possible to express the filter-update routine in terms of an associative operator using the formulation in Särkkä and García-Fernández (2021).<ref name=parallel>{{cite journal | author = Särkkä, S.| author2 = Ángel F. García-Fernández | year = 2021 | title = Temporal Parallelization of Bayesian Smoothers | journal = IEEE Transactions on Automatic Control | volume = 66 | issue = 1 | pages = 299–306 | doi = 10.1109/TAC.2020.2976316 | arxiv = 1905.13002 | s2cid = 213695560 }}</ref> The filter solution can then be retrieved by the use of a [[prefix sum]] algorithm which can be efficiently implemented on GPU.<ref name=prefix-nvida>{{cite web |url=https://developer.nvidia.com/gpugems/gpugems3/part-vi-gpu-computing/chapter-39-parallel-prefix-sum-scan-cuda |title=Parallel Prefix Sum (Scan) with CUDA |author=<!--Not stated--> |website=developer.nvidia.com/ |access-date=2020-02-21 |quote=The scan operation is a simple and powerful parallel primitive with a broad range of applications. In this chapter we have explained an efficient implementation of scan using CUDA, which achieves a significant speedup compared to a sequential implementation on a fast CPU, and compared to a parallel implementation in OpenGL on the same GPU. Due to the increasing power of commodity parallel processors such as GPUs, we expect to see data-parallel algorithms such as scan to increase in importance over the coming years.}}</ref> This reduces the [[computational complexity]] from <math>O(N)</math> in the number of time steps to <math>O(\log(N))</math>.