Average case complexity of elliptic partial differential equations

DOI10.1016/0885-064X(89)90028-9MaRDI QIDQ1262102zbMATH OpenOpenAlexFDO

Authors A. G. Werschulz

Publication date 1989

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(89)90028-9

zbMATH Keywords

almost optimal complexity algorithmaverage case settingfinite element methodworst case setting

Mathematics Subject Classification ID

Boundary value problems for second-order elliptic equations (35J25) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 953039
• What is the complexity of elliptic systems?
• Complexity of differential and integral equations
• scientific article; zbMATH DE number 50734
• The computational complexity of elliptic partial differential equations

Cites work

• Complexity of differential and integral equations
• Complexity of Indefinite Elliptic Problems
• Gaussian measures in Banach spaces
• scientific article; zbMATH DE number 3423512 (Why is no real title available?)
• scientific article; zbMATH DE number 3696612 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 3480903 (Why is no real title available?)
• scientific article; zbMATH DE number 3525575 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On kernels, eigenvalues, and eigenfunctions of operators related to elliptic problems
• On the average complexity of multivariate problems

Cited in

(5)

• What is the complexity of elliptic systems?
• Complexity and tractability for a class of elliptic partial integro-differential equations
• What is the Complexity of Related Elliptic, Parabolic, and Hyperbolic Problems?
• scientific article; zbMATH DE number 953039 (Why is no real title available?)
• The computational complexity of elliptic partial differential equations

This page was built for publication: Average case complexity of elliptic partial differential equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262102)