Numerical schemes and rates of convergence for the Hamilton–Jacobi equation continuum limit of nondominated sorting

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 languageEnglish (US)
Pages (from-to)819-856
Number of pages38
JournalNumerische Mathematik
Volume137
Issue number4
DOIs
StatePublished - Dec 1 2017

Fingerprint

Continuum Limit
Hamilton-Jacobi Equation
Sorting
Numerical Scheme
Rate of Convergence
Set of points
Euclidean space
n-dimensional
Numerical Simulation
Computer simulation

Keywords

  • 35D40
  • 35F21
  • 65N06

Cite this

@article{8946bf18db1c4575855bd1ffd75027e8,
title = "Numerical schemes and rates of convergence for the Hamilton–Jacobi equation continuum limit of nondominated sorting",
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.",
keywords = "35D40, 35F21, 65N06",
author = "Calder, {Jeffrey W}",
year = "2017",
month = "12",
day = "1",
doi = "10.1007/s00211-017-0895-5",
language = "English (US)",
volume = "137",
pages = "819--856",
journal = "Numerische Mathematik",
issn = "0029-599X",
publisher = "Springer New York",
number = "4",

}

TY - JOUR

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

AU - Calder, Jeffrey W

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

KW - 35D40

KW - 35F21

KW - 65N06

UR - http://www.scopus.com/inward/record.url?scp=85021076733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85021076733&partnerID=8YFLogxK

U2 - 10.1007/s00211-017-0895-5

DO - 10.1007/s00211-017-0895-5

M3 - Article

AN - SCOPUS:85021076733

VL - 137

SP - 819

EP - 856

JO - Numerische Mathematik

JF - Numerische Mathematik

SN - 0029-599X

IS - 4

ER -