claimroutineinferred_dep

Ordered approximations with error and time bounds

Approximating

A,B_0

costs

O(tp^{3/2+\delta}\alpha)

with error

<p^2

arithmetic cost and error of the factors

Claim·§8.1 The one-dimensional interface·inside lemOne-dimensional resampling without sorting

Statement (paper)

There are ordered-coordinate algorithms for

\widetilde{\mathsf S}'

\widetilde{\mathsf J}'

\widetilde{\mathsf D}'

with errors at most

16p

3p^2/4

4

and times

O(tp^{3/2+\delta}\alpha)

O(tp^{3/2+\delta}\alpha)

O(tp^{1+\delta})

respectively. The selection map

C

(selecting coordinates

q_j

with

q_0=0

q_{s-1}<t

q_{j+1}>q_j

) is computed exactly, with zero numerical error, in time

O(tp)

. Hence

\widetilde A=\widetilde{\mathsf S}'

and

\widetilde B_0=\widetilde{\mathsf D}'\widetilde{\mathsf J}'C

have errors less than

16p<p^2

and

4+3p^2/4<p^2

respectively, and the total cost is

O(tp^{3/2+\delta}\alpha)

In plain English

The scaled maps

\widetilde{\mathsf S}'

\widetilde{\mathsf J}'

\widetilde{\mathsf D}'

have ordered-coordinate algorithms with errors at most

16p

3p^2/4

4

and times

O(tp^{3/2+\delta}\alpha)

O(tp^{3/2+\delta}\alpha)

O(tp^{1+\delta})

, and the coordinate selection

C

is computed exactly in time

O(tp)

. Hence

\widetilde A=\widetilde{\mathsf S}'

and

\widetilde B_0=\widetilde{\mathsf D}'\widetilde{\mathsf J}'C

have errors below

p^2

and total cost

O(tp^{3/2+\delta}\alpha)

Why it's here

This turns the exact factorization

A=\mathsf S/2

B_0=\mathsf D'\mathsf J'C

into the fixed multitape algorithms the lemma requires. Since

C

adds no numerical error, the errors of the composed maps are the sum of those of the factors, and each stays below

p^2

. The time bounds of the factors add up to the lemma's

O(tp^{3/2+\delta}\alpha)

, apart from the tape-movement accounting, which is handled in a later claim.

Classified routine:

Error and cost bookkeeping that combines the earlier bounds for the factor maps S', J', D' with the standard rule that errors add under composition of contractions, adapting the resampling error analysis of Harvey–van der Hoeven (2021). The coordinate selection C is just exact copying of entries.

Uses

claimExact resampling identity with permutations retained

Used by

claimTape movement and Neumann iteration bounds

Sources

PaperOpen

Section: §8.1 The one-dimensional interface
Page: —
Label: —
Line: sections/07-resampling.tex:149

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Ordered numerical maps and selection error bounds" rests on claim-lem-no-sort-resampling-1