Algorithm Complexity

Study Notes

Each algorithm has a cost, which can be expressed in terms of computer operations, length of input, and other attributes.
Minimizing the cost is crucial in choosing an algorithm and searching for new ones.
The complexity of a problem is the lowest bound on the cost of any algorithm for its solution.

Classical complexity theory is based on the Turing machine and its framework of discrete operations on integer quantities.
It is at odds with the paradigm of numerical computation, which deals with continuous problems.
The main conundrum of classical complexity theory is the possible distinction between the class P (problems that can be computed in polynomial time) and the class NP (problems whose possible solution can be checked in polynomial time).

Real-number complexity has developed in distinct directions, including counting flops (floating-point operations) and information-based complexity.
Counting flops is relatively straightforward for finite algorithms, but it becomes less relevant when approximating continuous entities like differential and integral equations.
Information-based complexity introduces complexity to real-number calculations by using imperfect information in a structured setting to approximate the underlying continuous problem.

Lie-group solvers are a new breed of methods originating in geometric integration that respect the invariants of a problem, such as the Euclidean norm and eigenvalues.
Classical methods for differential equations do not respect nonlinear structures, making Lie-group solvers a more suitable approach.

Adaptivity is essential in numerical computation, involving the use of two intermeshed mechanisms: a monitor of the error incurred locally during the computation and a means to respond to this error bound by changing the algorithm's parameters.
Adaptivity is not limited to time-dependent problems and can be applied to other areas, such as lossy data compression using wavelet functions.

Stability theory is an important area of research, encompassing two broad concepts: well posedness and structural stability.
Well posedness refers to the property that small variations in initial and boundary conditions and in internal parameters induce small variations in the solution in compact intervals.
Structural stability refers to the property that small variations do not induce qualitative changes in global dynamics.
Discrete well posedness is not identical to continuous well posedness due to the extra parameters introduced by discretization.