- Complexity Theory of Numerical Analysis
- Monte Carlo and Quasi-Monte Carlo Algorithms
- Quantum Computation
Complexity Theory of Numerical Analysis
Information-based complexity theory (IBC) aims at finding the minimally necessary effort which is required for the numerical solution of problems of analysis. On a theoretical basis lower bounds are established. Upper bounds are derived by either investigating the efficiency and optimality of known algorithms or by developing new algorithms which are optimal in this setting. In a number of situations this approach led to completely new types of algorithms. Within this framework we study basic numerical problems like integration, approximation, parametric integration, solution of integral and differential equations.Monte Carlo and Quasi-Monte Carlo Algorithms
The main feature of stochastic (or Monte Carlo) algorithms is the use of randomness in the calculation process. Many highly complex applications, where traditional methods fail, can only be treated by stochastic techniques. We investigate the efficiency of such algorithms both in theory and in numerical experiments. On the basis of IBC results, new Monte Carlo algorithms for integration and integral equations are developed and tested for practical applications.A related field of research is that of quasi-Monte Carlo methods. Here random numbers are replaced by low discrepancy sequences, leading to deterministic algorithms. Discrepancy is a crucial quantity describing the efficiency (uniform distribution) of such sequences. We study various types of discrepancy from the theoretical point of view. We are also concerned with applications of low-discrepancy sequences.
Quantum Computation
A new challenging task is the investigation of the potential power of quantum computers. Worldwide huge efforts are concentrated on discrete and algebraic problems. Our research on quantum computing is concerned with the possible speed-up a quantum computer could bring for numerical problems of analysis. For this purpose we recently developed an IBC approach to quantum computation. Within this frame we seek to obtain matching lower and upper quantum complexity bounds, which also includes the construction of optimal quantum algorithms. First results concern numerical integration, which show that in the quantum setting considerable speed-ups are possible as compared to the (classical) deterministic and randomized setting.Journal of Complexity
Foundations of computational mathematics: FoCM homepage
Monte Carlo Methods and Applications
History of Mathematics
Quantum Computation
Quantum Physics