Fast Approximation for Toeplitz, Tridiagonal, Symmetric and Positive Definite Linear Systems that Grow Over Time

Linear systems with tridiagonal structures are very common in problems related not only to engineering, but chemistry, biomedical or finance, for example, real time cubic B-Spline interpolation of ND-images, real time processing of Electrocardiography (ECG) and hand drawing recognition. In those problems which the matrix is positive definite, it is possible to optimize the solution in O(n) time. This paper describes such systems whose size grows over time and proposes an approximation in O(1) time of such systems based on a series of previous approximations. In addition, it is described the development of the method and is proved that the proposed solution converges linearly to the optimal. A real-time cubic B-Spline interpolation of an ECG is computed with this proposal, for this application the proposed method shows a global relative error near to 10-6 and its computation is faster than traditional methods, as shown in the experiments.

@article{Mayorga2016,
  title     = {Fast Approximation for Toeplitz, Tridiagonal, Symmetric and Positive Definite Linear Systems that Grow Over Time},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {7},
  number    = {11},
  year      = {2016},
  publisher = {The Science and Information Organization},
  author    = {Pedro Mayorga and Alfonso Estudillo and A. Medina-Santiago and Jos´e V´azquez and Fernando Ramos},
  doi       = {10.14569/IJACSA.2016.071145},
  url       = {https://doi.org/10.14569/IJACSA.2016.071145}
}