Control theoretic analysis and design of numerical algorithms

Abstract

Many iterative numerical algorithms can be considered as dynamical systems. Since control theory deals with the study of dynamical systems, it has the potential to provide new insight, analysis tools and even new algorithms to the field of numerical analysis. Although the early knowledge of this observation, the research in this application area is scarce. In this thesis we use control theoretic ideas to study and design numerical algorithms. We will focus on developing analysis tools that could help speedup existing algorithms and design new algorithms that are fast or have a low computational time. Search for faster algorithms is an active research area in the fields of numerical analysis and computing, which is driven by the requirements of many applications. One of the ways to speedup an algorithm is to design a custom computational hardware for it. For several algorithms it has been shown that a customized computational hardware can give significant speedups over general processors. One of the parameters in custom hardware design is the choice of number representation. While in general purpose computational hardware this is fixed to a 64 bit floating point with a precision of 53 bits, in custom hardware design any number of bits can be chosen. A circuit in lower precision utilizes less hardware resources on a chip, allowing more parallel computational blocks to be built on the chip that could speedup calculations in an algorithm. However, reducing the precision increases the errors in computations. There is a trade-off between speed and accuracy of computations and one would like to know what precision is just enough for a given algorithm to guarantee solutions of a desired accuracy. A bound on the error in the solution obtained by an algorithm as a function of precision would be useful in the decision of precision. Such a bound is called forward error bound and the process of finding it is called forward error analysis. In this thesis we use control theoretic ideas to present forward error analysis schemes for algorithms in finite precision. While forward error analysis is a standard technique in numerical analysis, the objective is usually to just show that such a bound exists. Whereas, for our application we would like to find a tight bound. In this thesis we present three control theoretic forward analysis schemes. The first schemes is based on the control tools of l8-stability and input-to-state stability. The other two schemes are based on results from the study of quantization effects in control systems. The proposed schemes are applied on the successive iteration method and the classical iterative method for solving a system of linear equation. The obtained bounds are shown to be tighter than the existing bounds in the numerical analysis literature. While most of the efforts to speedup an algorithm are to customize the hardware for it, we should also look for new algorithms that are more suitable for hardware, i.e. the design of algorithms should be aware of what type of computations can be easily accelerated in hardware. In this thesis we use control theoretic ideas to present a new algorithm for solving a positive definite system of linear equations. The proposed algorithm in highly parallelizable and can effectively take advantage of parallel computational hardware. It is shown that the proposed algorithm has lower time complexity than other state of the art algorithms for the case of parallel computing.