Talk by Klaus Mosegaard, University of Copenhagen

The search for solutions to nonlinear problems - why do algorithms often fail?

Abstract

Some inverse problems in geophysics suffer from a ‘brick wall effect’, namely that the problem is practically solvable up to a certain number of unknown model parameters, but requires excessive computer resources if only a few more model parameters are added. Such problems seem hard, since an increase in the number of model parameters, due to an extension of the Earth model, apparently results in an (at least) exponential increase in computation time.

Could this effect be a limitation of existing algorithms, or is it a fundamental property of some highly nonlinear inverse problems? If the latter holds true, we must accept in-principle limitations to what can be obtained even from the fastest computers running optimal algorithms.

We shall look into this nature of this problem and see how algorithm developers have seeked to ameliorate the performance of current methods. Using information arguments we shall argue that only problem-specific algorithms are able to turn hard inverse problems into polynomial problems.