Average case complexity of elliptic partial differential equations (Q1262102)

The author obtains tight complexity bounds for the approximate solution of elliptic partial differential equations in the worst case setting, and finds conditions that are necessary and sufficient for the finite element method to be an almost optimal complexity algorithm. Since these bounds show that elliptic partial differential equations are intractable in the worst case setting, it is natural to seek another setting in which partial differential equations are tractable. With this in mind, the author looks at the average case setting. Moreover, the author shows that the finite element method with properly chosen parameters is an almost optimal complexity algorithm in the average case.