Numerical schemes and rates of convergence for the Hamilton-Jacobi\n equation continuum limit of nondominated sorting

2015/08/06 by Jeff Calder, Calder, Jeff
Mathematics · #35D40 #35F21 #65N06 #Analysis of PDEs (math.AP) #FOS: Mathematics #Morphological variations and asymmetry #Numerical Analysis (math.NA) #Point processes and geometric inequalities #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1508.01557

openalex publication_date 2015/08/06 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

Nondominated sorting arranges a set of points in Euclidean space into layers\nby repeatedly removing the coordinatewise minimal elements. It was recently\nshown that nondominated sorting of random points has a Hamilton-Jacobi equation\ncontinuum limit. The obvious numerical scheme for this PDE has a slow\nconvergence rate of O(h¹/n) for a grid of spacing h>0 in dimension n. In this\npaper, we introduce two new numerical schemes that have formal rates of O(h)\nand we prove the usual O(h¹/2) theoretical rates. We also present the results\nof numerical simulations illustrating the difference between the formal and\ntheoretical rates.\n

Related

• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• A Hamilton-Jacobi equation for the continuum limit of non-dominated\n sorting
• High-order filtered schemes for the Hamilton-Jacobi continuum limit of\n nondominated sorting
• A PDE-based approach to non-dominated sorting
• Error estimates and convergence rates for the stochastic homogenization of Hamilton-Jacobi equations