Abstract
Non-dominated sorting arranges a set of points in n-dimensional Euclidean space into layers by repeatedly removing the coordinatewise minimal elements. It was recently shown that nondominated sorting of random points has a Hamilton–Jacobi equation continuum limit. The obvious numerical scheme for this PDE has a slow convergence rate of O(h1n). In this paper, we introduce two new numerical schemes that have formal rates of O(h) and we prove the usual O(h) theoretical rates. We also present the results of numerical simulations illustrating the difference between the formal and theoretical rates.
Original language | English (US) |
---|---|
Pages (from-to) | 819-856 |
Number of pages | 38 |
Journal | Numerische Mathematik |
Volume | 137 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1 2017 |
Bibliographical note
Publisher Copyright:© 2017, Springer-Verlag GmbH Deutschland.
Keywords
- 35D40
- 35F21
- 65N06