text: Proton Density at t = 60T for Case I Proton Density at t = 60T for Case II 0 0 5 10 5 10 (a) (b) 8 8 0 6 0 6 4 4 −5 2 −5 2 0 20 40 60 80 0 20 40 60 80 Proton Density at t = 80T for Case I Proton Density at t = 80T for Case II 0 0 5 10 5 10 (c) (d) 8 8 0 6 0 6 4 4 −5 2 −5 2 0 20 40 60 80 0 20 40 60 80 x(λ ) x(λ ) 0 0 FIG. 2: (Color online) The proton density of the case I [(a) and (c)] and the case II [(b) and (d)] at t = 60T [(a) and (b)] and 80T [(c) and (d)]. Here the proton density is normalized by n . 0 0 c contrast the proton density decreases signiﬁcantly and bunch also diﬀuses seriously in the transverse direction in the case I. To demonstrate the enhanced acceleration eﬀect by using the cone-capillary, the energy spectra and angular distribution of the protons are shown in Fig. 3. For the energy spectra they are plotted in Fig. 3(a) and 3(b) at diﬀerent time. It shows that there are a monoenergetic proton bunches in both cases at t = 60T . Similarly as in 0 the density the better quality seems to be got in case I at this relative earlier time. For ∼ example, see Fig. 3(a), the bunch quality of a peak energy E 1.53 GeV with energy k ∼ ∼ spread 5% in the case I is indeed better than that of a peak energy E 1.47 GeV with k ∼ energy spread 12% in the case II. However with time increasing, the situation is reversed again for the energy spectra. In fact the monoenergetic peak structure disappears evenly in ∼ the case I at t = 80T while it remains a good quality by a peak energy E 1.51 GeV with 0 k ∼ energy spread 7% in the case II, see Fig. 3(a), even if the protons have moved out from the capillary. On the other hand the protons number at the monoenergetic peak in the case II is almost three times higher than that in the case I. For the angular distribution they are plotted in Fig. 3(c) and 3(d). The momentum − angle of protons is deﬁned by θ = tan 1(p /p ), where p and p are the momentum of the y x y x protons in the transverse y-axis and longitudinal x-axis, respectively. In the case II, it is 6 ) λ(y ) λ(y 0 0 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proton

text: Density

text: at

text: t

text: for

text: Case

text: I

text: Proton

text: Density

text: at

text: t

text: for

text: Case

text: II

text: (a)

text: (b)

text: −5

text: −5

text: Proton

text: Density

text: at

text: t

text: for

text: Case

text: I

text: Proton

text: Density

text: at

text: t

text: for

text: Case

text: II

text: (c)

text: (d)

text: −5

text: −5

text: x(λ

text: x(λ

text: FIG.

text: (Color

text: online)

text: The

text: proton

text: density

text: of

text: the

text: case

text: I

text: [(a)

text: and

text: (c)]

text: and

text: the

text: case

text: II

text: [(b)

text: and

text: (d)]

text: at

text: t

text: [(a)

text: and

text: (b)]

text: and

text: [(c)

text: and

text: (d)].

text: Here

text: the

text: proton

text: density

text: is

text: normalized

text: by

text: n

text: c

text: contrast

text: the

text: proton

text: density

text: decreases

text: signiﬁcantly

text: and

text: bunch

text: also

text: diﬀuses

text: seriously

text: in

text: the

text: transverse

text: direction

text: in

text: the

text: case

text: I.

text: To

text: demonstrate

text: the

text: enhanced

text: acceleration

text: eﬀect

text: by

text: using

text: the

text: cone-capillary,

text: the

text: energy

text: spectra

text: and

text: angular

text: distribution

text: of

text: the

text: protons

text: are

text: shown

text: in

text: Fig.

text: For

text: the

text: energy

text: spectra

text: they

text: are

text: plotted

text: in

text: Fig.

text: and

text: at

text: diﬀerent

text: time.

text: It

text: shows

text: that

text: there

text: are

text: a

text: monoenergetic

text: proton

text: bunches

text: in

text: both

text: cases

text: at

text: t

text: Similarly

text: as

text: in

text: the

text: density

text: the

text: better

text: quality

text: seems

text: to

text: be

text: got

text: in

text: case

text: I

text: at

text: this

text: relative

text: earlier

text: time.

text: For

text: example,

text: see

text: Fig.

text: the

text: bunch

text: quality

text: of

text: a

text: peak

text: energy

text: E

text: GeV

text: with

text: energy

text: k

text: spread

text: in

text: the

text: case

text: I

text: is

text: indeed

text: better

text: than

text: that

text: of

text: a

text: peak

text: energy

text: E

text: GeV

text: with

text: k

text: energy

text: spread

text: in

text: the

text: case

text: II.

text: However

text: with

text: time

text: increasing,

text: the

text: situation

text: is

text: reversed

text: again

text: for

text: the

text: energy

text: spectra.

text: In

text: fact

text: the

text: monoenergetic

text: peak

text: structure

text: disappears

text: evenly

text: in

text: the

text: case

text: I

text: at

text: t

text: while

text: it

text: remains

text: a

text: good

text: quality

text: by

text: a

text: peak

text: energy

text: E

text: GeV

text: with

text: k

text: energy

text: spread

text: in

text: the

text: case

text: II,

text: see

text: Fig.

text: even

text: if

text: the

text: protons

text: have

text: moved

text: out

text: from

text: the

text: capillary.

text: On

text: the

text: other

text: hand

text: the

text: protons

text: number

text: at

text: the

text: monoenergetic

text: peak

text: in

text: the

text: case

text: II

text: is

text: almost

text: three

text: times

text: higher

text: than

text: that

text: in

text: the

text: case

text: I.

text: For

text: the

text: angular

text: distribution

text: they

text: are

text: plotted

text: in

text: Fig.

text: and

text: The

text: momentum

text: angle

text: of

text: protons

text: is

text: deﬁned

text: by

text: θ

text: tan

text: /p

text: where

text: p

text: and

text: p

text: are

text: the

text: momentum

text: of

text: the

text: y

text: x

text: y

text: x

text: protons

text: in

text: the

text: transverse

text: y-axis

text: and

text: longitudinal

text: x-axis,

text: respectively.

text: In

text: the

text: case

text: II,

text: it

text: is

text: λ(y

text: λ(y

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:80) (cid:80) (cid:80) (cid:80) | Proof. First, we show by strong induction over t that pk ∈ s(d)b(d)t for all | d D t < j. For t = 0 we have pk ∈ s(d)a(0, 0) and since gcd(pk, a(0, 0)) = 1 we | d D | get pk ∈ s(d). Now, assume that pk ∈ s(d)b(d)t for all t satisfying ≤ d D d D (cid:88) (cid:88) 0 t < m for some m < j. Then 0 ≡ w(m) = (cid:88) s(d) m a(t, m)b(d)t ∈ d D t=0 ≡ (cid:80) a(m, m)s(d)b(d)m (mod pk) ∈ d(cid:80)D | so pk ∈ s(d)b(d)m as gcd(a(m, m), pk) = 1. d D | Second, the fact that pk (cid:88) ∈ s(cid:88)(d)b(d)t for all t < j yields d D j w(j) = (cid:88) s(d) a(t, j)b(d)t ∈ d D t=0 ≡ a(j, j)s(d)b(d)j (mod pk). ∈ d D Having proved the lemma we now turn to the main technical theorem of the section from which the remaining results follow naturally. ≤ Theorem 3.2. Let p be an odd prime; r > 2 and n p + 1 be given; and m = | | (cid:104) (cid:105) ∈ (m , . . . , m ). Suppose that pk r and pk B 1, a for every s (Z )p+1 1 n (cid:18) (cid:19) (r;s) r and every a < n. Then (cid:89) − − (cid:104) (cid:105) ≡ r + n 2 n 1 − B 1, n − m 1 (mod pk). (r;m) n 1 k k=2 Proof. For every vector m we can reduce the problem to considering a vector (cid:48) (cid:48) (cid:48) (cid:48) m which satisﬁes m = m = m = 1 as follows. First, recall that no matter 1 2 n what vector we consider, we can always assume without loss of generality that its ﬁrst and last entry is 1 since it does not aﬀect any of the sides of the above expression by Lemma 2.14. Second, as in the proof of Corollary 2.16 we can − (cid:48) − · (cid:48) multiply m by a m 1 to get m = m 1 m, which means that m = 1. Then 2 2 (cid:104) (cid:105) (cid:104) 2(cid:105) the left ha(cid:18)nd side wil(cid:19)l not change (cid:18)since B(r;m(cid:19)) 1, n = B(r;m(cid:48)) 1, n by Lemma 2.15 and the right hand(cid:89)side will satisfy (cid:89) − − − − r + n 2 n 1 − ≡ r + n 2 n 1 − − (cid:0)m 1 (cid:1) − bm 1 (mod pk) n 1 k n 1 k (cid:0) (cid:1) k=2 k=2 | − − ≡ since for n < p + 1, pk r+−n 2 and for n = p + 1, bn 2 1 (mod p) and − | − n 1 (cid:48) (cid:48) pk 1 r+−n 2 . Now, assuming m = m = 1 yields the above. Thus, for the n 1 1 n 11 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: Proof.

text: First,

text: we

text: show

text: by

text: strong

text: induction

text: over

text: t

text: that

text: pk

text: s(d)b(d)t

text: for

text: all

text: d

text: D

text: t

text: j.

text: For

text: t

text: we

text: have

text: pk

text: and

text: since

text: gcd(pk,

text: we

text: d

text: D

text: get

text: pk

text: s(d).

text: Now,

text: assume

text: that

text: pk

text: s(d)b(d)t

text: for

text: all

text: t

text: satisfying

text: d

text: D

text: d

text: D

text: t

text: m

text: for

text: some

text: m

text: j.

text: Then

text: w(m)

text: s(d)

text: m

text: a(t,

text: m)b(d)t

text: d

text: D

text: a(m,

text: m)s(d)b(d)m

text: (mod

text: pk)

text: so

text: pk

text: s(d)b(d)m

text: as

text: gcd(a(m,

text: m),

text: pk)

text: d

text: D

text: Second,

text: the

text: fact

text: that

text: pk

text: for

text: all

text: t

text: j

text: yields

text: d

text: D

text: j

text: w(j)

text: s(d)

text: a(t,

text: j)b(d)t

text: d

text: D

text: a(j,

text: j)s(d)b(d)j

text: (mod

text: pk).

text: d

text: D

text: Having

text: proved

text: the

text: lemma

text: we

text: now

text: turn

text: to

text: the

text: main

text: technical

text: theorem

text: of

text: the

text: section

text: from

text: which

text: the

text: remaining

text: results

text: follow

text: naturally.

text: Theorem

text: Let

text: p

text: be

text: an

text: odd

text: prime;

text: r

text: and

text: n

text: p

text: be

text: given;

text: and

text: m

text: (m

text: m

text: Suppose

text: that

text: pk

text: r

text: and

text: pk

text: B

text: a

text: for

text: every

text: s

text: (Z

text: n

text: (r;s)

text: r

text: and

text: every

text: a

text: n.

text: Then

text: r

text: n

text: n

text: B

text: n

text: m

text: (mod

text: pk).

text: (r;m)

text: n

text: k

text: Proof.

text: For

text: every

text: vector

text: m

text: we

text: can

text: reduce

text: the

text: problem

text: to

text: considering

text: a

text: vector

text: m

text: which

text: satisﬁes

text: m

text: m

text: m

text: as

text: follows.

text: First,

text: recall

text: that

text: no

text: matter

text: n

text: what

text: vector

text: we

text: consider,

text: we

text: can

text: always

text: assume

text: without

text: loss

text: of

text: generality

text: that

text: its

text: ﬁrst

text: and

text: last

text: entry

text: is

text: since

text: it

text: does

text: not

text: aﬀect

text: any

text: of

text: the

text: sides

text: of

text: the

text: above

text: expression

text: by

text: Lemma

text: Second,

text: as

text: in

text: the

text: proof

text: of

text: Corollary

text: we

text: can

text: multiply

text: m

text: by

text: a

text: m

text: to

text: get

text: m

text: m

text: m,

text: which

text: means

text: that

text: m

text: Then

text: the

text: left

text: side

text: not

text: change

text: n

text: n

text: by

text: Lemma

text: and

text: the

text: right

text: will

text: satisfy

text: r

text: n

text: n

text: r

text: n

text: n

text: bm

text: (mod

text: pk)

text: n

text: k

text: n

text: k

text: since

text: for

text: n

text: p

text: pk

text: r+−n

text: and

text: for

text: n

text: p

text: bn

text: (mod

text: p)

text: and

text: n

text: pk

text: r+−n

text: Now,

text: assuming

text: m

text: m

text: yields

text: the

text: above.

text: Thus,

text: for

text: the

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: To apply Lemma 3.1 again we write (cid:18) (cid:19) s˜(d) := s(d)d, l + 1 a˜(t, l) := − (l + 1)!B − , l t l t − ˜b(d) := [m −1 d] , n j r (cid:124) (cid:123)(cid:122) (cid:125) and considering the vectors v = (m , m , . . . , m − , 1, . . . , 1) one ﬁnds: (cid:88) (cid:88) l+1 1 2 n j l+1 − r 1 l w˜(l) := s˜(d) a˜(t, l)˜b(d)t d=0 t=0 ≡ − − (cid:104) − (cid:105) (ml −1 ) 1(l + 1)!2B 1, n j + l + 1 (mod pk). n j (r;vl+1) ≡(cid:0) (cid:1)− − (cid:104) − (cid:105) (ml −1 ) 1(l + 1)!2B 1, n j + l + 1 (mod pk). n j (r;nj) ≤ − − ≤ Now, a˜(l, l) = l+1 (l + 1)!B = (l + 1)! so for 0 l < j 1 < n 1 p we 0 0 | (cid:104) − (cid:105) have gcd(a˜(l, l), p) = 1. Further, by assumption pk B 1, n j + l + 1 for ≤ − | ≤ − (r;nj) 0 l < j 1, so pk w˜(l) for 0 l < j 1. Thus, Lemma 3.1 yields − − (cid:104) (cid:105) (cid:88) − (mj −2) 1j!2B 1, n = w˜(j 1) n j (r;nj) − ≡ r 1 − − − − s(d)da˜(j 1, j 1)(m −1 d)j 1 (cid:88) n j q=0 − ≡ − r 1 m1−j j!s(d)dj (mod pk) n j q=0 (cid:88) This means that − (cid:104) (cid:105) ≡ − r 1 − B 1, n m −1 j! 1s(d)dj (mod pk), (r;nj) n j q=0 − − ≤ where we note that j! 1 is well-deﬁned because j < n 1 p so gcd(j!, p) = 1. Since s(d) only depends on m , . . . , m − − , it is clear that we can ﬁnd g 1 n j 1 j (cid:101) satisfying (1) and we are done. (cid:45) Having proved the above theorem we can apply it to ﬁnd ϕ(r) whenever 4 r. We ﬁrst use the theorem to prove the following lemma, which will give the ﬁrst half of the proof. || ∈ N Lemma 3.3. Let r > 2, p be an odd prime, and pk r for some k . For − every vector m with entries in Z and every pair a, b satisfying 0 < b a < p r we have | (cid:104) (cid:105) pk B a, b . (r;m) 15 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: To

text: apply

text: Lemma

text: again

text: we

text: write

text: s˜(d)

text: s(d)d,

text: l

text: a˜(t,

text: l)

text: (l

text: l

text: t

text: l

text: t

text: ˜b(d)

text: [m

text: −1

text: d]

text: n

text: j

text: r

text: and

text: considering

text: the

text: vectors

text: v

text: (m

text: m

text: m

text: one

text: ﬁnds:

text: n

text: j

text: r

text: l

text: w˜(l)

text: s˜(d)

text: a˜(t,

text: l)˜b(d)t

text: (ml

text: −1

text: n

text: j

text: l

text: (mod

text: pk).

text: n

text: j

text: (ml

text: −1

text: n

text: j

text: l

text: (mod

text: pk).

text: n

text: j

text: (r;nj)

text: Now,

text: a˜(l,

text: l)

text: (l

text: (l

text: so

text: for

text: l

text: j

text: n

text: p

text: we

text: have

text: gcd(a˜(l,

text: l),

text: p)

text: Further,

text: by

text: assumption

text: pk

text: B

text: n

text: j

text: l

text: for

text: (r;nj)

text: l

text: j

text: so

text: pk

text: w˜(l)

text: for

text: l

text: j

text: Thus,

text: Lemma

text: yields

text: (mj

text: n

text: w˜(j

text: n

text: j

text: (r;nj)

text: r

text: s(d)da˜(j

text: j

text: −1

text: d)j

text: n

text: j

text: r

text: j!s(d)dj

text: (mod

text: pk)

text: n

text: j

text: This

text: means

text: that

text: r

text: B

text: n

text: m

text: −1

text: j!

text: (mod

text: pk),

text: (r;nj)

text: n

text: j

text: where

text: we

text: note

text: that

text: j!

text: is

text: well-deﬁned

text: because

text: j

text: n

text: p

text: so

text: gcd(j!,

text: p)

text: Since

text: s(d)

text: only

text: depends

text: on

text: m

text: m

text: it

text: is

text: clear

text: that

text: we

text: can

text: ﬁnd

text: g

text: n

text: j

text: j

text: satisfying

text: and

text: we

text: are

text: done.

text: Having

text: proved

text: the

text: above

text: theorem

text: we

text: can

text: apply

text: it

text: to

text: ﬁnd

text: ϕ(r)

text: whenever

text: r.

text: We

text: ﬁrst

text: use

text: the

text: theorem

text: to

text: prove

text: the

text: following

text: lemma,

text: which

text: will

text: give

text: the

text: ﬁrst

text: half

text: of

text: the

text: proof.

text: N

text: Lemma

text: Let

text: r

text: p

text: be

text: an

text: odd

text: prime,

text: and

text: pk

text: r

text: for

text: some

text: k

text: For

text: every

text: vector

text: m

text: with

text: entries

text: in

text: Z

text: and

text: every

text: pair

text: a,

text: b

text: satisfying

text: b

text: a

text: p

text: r

text: we

text: have

text: pk

text: B

text: a,

text: b

text: (r;m)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: to incorrect inferences. The example we take here is that of PDE constrained Bayesian inverse problems, in which we wish to estimate parameters of a PDE model in a Bayesian framework, based on observations of a system which is believed to be described by the underlying PDE. In such problems it has been shown that employing an inaccurate PDE solver in the sampling can lead to incorrect inferences in the inverse problem [3]. There has been recent interest in construction of probabilistic solvers for PDEs. Work by [3] constructs a nonparametric posterior distribution for ODEs and PDEs by injecting noise into standard numerical solvers in such a way as to maintain the convergence properties of these solvers. In [8], the authors discuss a meshless method which is similar to the method discussed herein by modelling the forcing of the PDE. This is developed in [9], which discusses a methodology for probabilistic solution of PDEs by an hierarchical game-theoretic argument. These latter two approaches do not examine application to inverse problems, however. Work from [1] discusses the interpretation of symmetric collocation as the mean func- tion of a Gaussian process prior after conditioning on observed values of the forcing, but applies this methodology predominantly to stochastic diﬀerential equations. 1.1 Structure of the Paper We begin by introducing the concept of a probabilistic meshless method and giving some theoretical results related to it. We then show how the posterior measure over the forward solution of the PDE can be propagated to the posterior measure over param- eters in a Bayesian inverse problem. Finally we present some numerical results for a challenging nonlinear inverse problem given by the steady-state Allen–Cahn equations. Proofs for the presented theorems are omitted, and can be found in [2]. 2 The Probabilistic Meshless Method We now introduce the concept of a probabilistic meshless method (PMM). Consider R an open, bounded subset D of d with Lipschitz boundary ∂D. We seek a solution ∈ u H(D), some Hilbert space of functions deﬁned over D, of the following system of operator equations A ∈ u(x) = g(x) x D B ∈ u(x) = b(x) x ∂D. (1) A → B → ∈ ∈ A Here : H(D) HA(D) and : H(D) HB(D) with g HA(D) and b HB(D). B is associated with a partial diﬀerential operator and is associated with the boundary conditions of the system. For notational simplicity we restrict attention to systems of two operators, however the methods discussed can be generalised to an arbitrary number of operator equations. We proceed in a Bayesian setting by placing a prior measure Π on u, and determining u its posterior distribution based on a ﬁnite number of observations of the system given in Eq. 1. In this work we focus on the most direct observations of said system; namely, we { } A ⊂ { } B ⊂ choose sets of design points x A = X D, x B = X ∂D for i = 1, . . . , mA, i, 0 j, 0 j = 1, . . . , mB. We then evaluate the right-hand-side corresponding to each of the operators in the system at these points; g = [g(x A)], b = [b(x B)]. i, i, 2

text: to

text: incorrect

text: inferences.

text: The

text: example

text: we

text: take

text: here

text: is

text: that

text: of

text: PDE

text: constrained

text: Bayesian

text: inverse

text: problems,

text: in

text: which

text: we

text: wish

text: to

text: estimate

text: parameters

text: of

text: a

text: PDE

text: model

text: in

text: a

text: Bayesian

text: framework,

text: based

text: on

text: observations

text: of

text: a

text: system

text: which

text: is

text: believed

text: to

text: be

text: described

text: by

text: the

text: underlying

text: PDE.

text: In

text: such

text: problems

text: it

text: has

text: been

text: shown

text: that

text: employing

text: an

text: inaccurate

text: PDE

text: solver

text: in

text: the

text: sampling

text: can

text: lead

text: to

text: incorrect

text: inferences

text: in

text: the

text: inverse

text: problem

text: There

text: has

text: been

text: recent

text: interest

text: in

text: construction

text: of

text: probabilistic

text: solvers

text: for

text: PDEs.

text: Work

text: by

text: constructs

text: a

text: nonparametric

text: posterior

text: distribution

text: for

text: ODEs

text: and

text: PDEs

text: by

text: injecting

text: noise

text: into

text: standard

text: numerical

text: solvers

text: in

text: such

text: a

text: way

text: as

text: to

text: maintain

text: the

text: convergence

text: properties

text: of

text: these

text: solvers.

text: In

text: the

text: authors

text: discuss

text: a

text: meshless

text: method

text: which

text: is

text: similar

text: to

text: the

text: method

text: discussed

text: herein

text: by

text: modelling

text: the

text: forcing

text: of

text: the

text: PDE.

text: This

text: is

text: developed

text: in

text: which

text: discusses

text: a

text: methodology

text: for

text: probabilistic

text: solution

text: of

text: PDEs

text: by

text: an

text: hierarchical

text: game-theoretic

text: argument.

text: These

text: latter

text: two

text: approaches

text: do

text: not

text: examine

text: application

text: to

text: inverse

text: problems,

text: however.

text: Work

text: from

text: discusses

text: the

text: interpretation

text: of

text: symmetric

text: collocation

text: as

text: the

text: mean

text: func-

text: tion

text: of

text: a

text: Gaussian

text: process

text: prior

text: after

text: conditioning

text: on

text: observed

text: values

text: of

text: the

text: forcing,

text: but

text: applies

text: this

text: methodology

text: predominantly

text: to

text: stochastic

text: diﬀerential

text: equations.

text: Structure

text: of

text: the

text: Paper

text: We

text: begin

text: by

text: introducing

text: the

text: concept

text: of

text: a

text: probabilistic

text: meshless

text: method

text: and

text: giving

text: some

text: theoretical

text: results

text: related

text: to

text: it.

text: We

text: then

text: show

text: how

text: the

text: posterior

text: measure

text: over

text: the

text: forward

text: solution

text: of

text: the

text: PDE

text: can

text: be

text: propagated

text: to

text: the

text: posterior

text: measure

text: over

text: param-

text: eters

text: in

text: a

text: Bayesian

text: inverse

text: problem.

text: Finally

text: we

text: present

text: some

text: numerical

text: results

text: for

text: a

text: challenging

text: nonlinear

text: inverse

text: problem

text: given

text: by

text: the

text: steady-state

text: Allen–Cahn

text: equations.

text: Proofs

text: for

text: the

text: presented

text: theorems

text: are

text: omitted,

text: and

text: can

text: be

text: found

text: in

text: The

text: Probabilistic

text: Meshless

text: Method

text: We

text: now

text: introduce

text: the

text: concept

text: of

text: a

text: probabilistic

text: meshless

text: method

text: (PMM).

text: Consider

text: R

text: an

text: open,

text: bounded

text: subset

text: D

text: of

text: d

text: with

text: Lipschitz

text: boundary

text: ∂D.

text: We

text: seek

text: a

text: solution

text: u

text: H(D),

text: some

text: Hilbert

text: space

text: of

text: functions

text: deﬁned

text: over

text: D,

text: of

text: the

text: following

text: system

text: of

text: operator

text: equations

text: A

text: u(x)

text: g(x)

text: x

text: D

text: B

text: u(x)

text: b(x)

text: x

text: ∂D.

text: A

text: B

text: A

text: Here

text: H(D)

text: HA(D)

text: and

text: H(D)

text: HB(D)

text: with

text: g

text: HA(D)

text: and

text: b

text: HB(D).

text: B

text: is

text: associated

text: with

text: a

text: partial

text: diﬀerential

text: operator

text: and

text: is

text: associated

text: with

text: the

text: boundary

text: conditions

text: of

text: the

text: system.

text: For

text: notational

text: simplicity

text: we

text: restrict

text: attention

text: to

text: systems

text: of

text: two

text: operators,

text: however

text: the

text: methods

text: discussed

text: can

text: be

text: generalised

text: to

text: an

text: arbitrary

text: number

text: of

text: operator

text: equations.

text: We

text: proceed

text: in

text: a

text: Bayesian

text: setting

text: by

text: placing

text: a

text: prior

text: measure

text: Π

text: on

text: u,

text: and

text: determining

text: u

text: its

text: posterior

text: distribution

text: based

text: on

text: a

text: ﬁnite

text: number

text: of

text: observations

text: of

text: the

text: system

text: given

text: in

text: Eq.

text: In

text: this

text: work

text: we

text: focus

text: on

text: the

text: most

text: direct

text: observations

text: of

text: said

text: system;

text: namely,

text: we

text: A

text: B

text: choose

text: sets

text: of

text: design

text: points

text: x

text: A

text: X

text: D,

text: x

text: B

text: X

text: ∂D

text: for

text: i

text: mA,

text: i,

text: j,

text: j

text: mB.

text: We

text: then

text: evaluate

text: the

text: right-hand-side

text: corresponding

text: to

text: each

text: of

text: the

text: operators

text: in

text: the

text: system

text: at

text: these

text: points;

text: g

text: [g(x

text: A)],

text: b

text: [b(x

text: B)].

text: i,

text: i,


text: It remains to specify our prior distribution. Here we choose a Gaussian process prior GP Π = (m, k). Recall that a Gaussian Process is characterised by its mean function m u ∼ GP and its covariance function k, and the property that, if u (m, k) then for any set { } ⊂ R of points x d, i = 1, . . . , n i ∼ N u(X) (µ, Σ) [µ] = m(x ) i i [Σ] = k(x , x ) ij i j (cid:20) (cid:21) As is common in the literature we will use a (cid:2)centred(cid:3) Gaussian process prior; Π = GP u (0, k). Deﬁne A L L A B = B ¯ = ¯ ¯ { } { } and furthermore for sets X = x , i = 1, . . . , N, Y = y , j = 1, . . . , M let K(X, Y ) i j denote the Gram matrix of K applied to X and Y ; [K(X, Y )] = k(x , y ). Similarly A A (cid:20) ij (cid:21) i j [ K(X, Y )] = k(x , y ), etc. Then ij i j AA A A AB A B LL (cid:20) ¯K(X , X(cid:21) ) ¯K(X , X ) ¯K(X , X ) = BA 0B A0 BB 0B B0 0 0 ¯K(X , X ) ¯K(X , X ) 0 0 0 0 A A L (cid:2) K(X , X) (cid:3) K(X , X) = B 0B 0 K(X , X) 0 L A A B B ¯K(X, X ) = ¯K(X, X ) ¯K(X, X ) 0 0 0 Here X is to be interpreted as a set of points at which we evaluate those functions drawn A∪ B from the posterior distribution, in contrast with X = X X which is the set of points 0 0 0 at which evaluations of the forcing terms are taken. A B Proposition 1 (Probabilistic Meshless Method). Assume and are linear operators. Then the posterior distribution Πg,b over the solution of the PDE, conditional on the data ∼ u g, b is such that, for u Πg,b we have u (cid:2) (cid:3) (cid:2) (cid:3) ∼ N u(X) (µ, Σ) (cid:2) (cid:3) L LL − (cid:62) (cid:62) (cid:62) µ = ¯K(X, X ) ¯K(X , X ) 1 g b (2) 0 0 0 − L LL − L Σ = K(X, X) ¯K(X, X ) ¯K(X , X ) 1 K(X , X) 0 0 0 0 Note that the mean function in Eq. 2 is the same as the numerical solution to the PDE that would be obtained using the method of symmetric collocation [5]. Thus far we not discussed the choice of prior covariance k. There are several inter- esting choices in the literature. Work in [8] proposes use of a covariance which encodes information about the system through its Green’s function; [2] examined the properties of this choice in more detail. However, reliance on the Green’s function, which is not in general available in closed-form for complex systems, is a signiﬁcant drawback. In practice we will generally posit a prior covariance directly by examining the system in question and selecting a prior which encodes a suitable level of diﬀerentiability. 3

text: It

text: remains

text: to

text: specify

text: our

text: prior

text: distribution.

text: Here

text: we

text: choose

text: a

text: Gaussian

text: process

text: prior

text: GP

text: Π

text: (m,

text: k).

text: Recall

text: that

text: a

text: Gaussian

text: Process

text: is

text: characterised

text: by

text: its

text: mean

text: function

text: m

text: u

text: GP

text: and

text: its

text: covariance

text: function

text: k,

text: and

text: the

text: property

text: that,

text: if

text: u

text: (m,

text: k)

text: then

text: for

text: any

text: set

text: R

text: of

text: points

text: x

text: d,

text: i

text: n

text: i

text: N

text: u(X)

text: (µ,

text: Σ)

text: [µ]

text: m(x

text: i

text: i

text: [Σ]

text: k(x

text: x

text: ij

text: i

text: j

text: As

text: is

text: common

text: in

text: the

text: literature

text: we

text: will

text: use

text: a

text: Gaussian

text: process

text: prior;

text: Π

text: GP

text: u

text: k).

text: Deﬁne

text: A

text: L

text: L

text: A

text: B

text: B

text: and

text: furthermore

text: for

text: sets

text: X

text: x

text: i

text: N,

text: Y

text: y

text: j

text: M

text: let

text: K(X,

text: Y

text: i

text: j

text: denote

text: the

text: Gram

text: matrix

text: of

text: K

text: applied

text: to

text: X

text: and

text: Y

text: [K(X,

text: Y

text: k(x

text: y

text: Similarly

text: A

text: A

text: ij

text: i

text: j

text: K(X,

text: Y

text: k(x

text: y

text: etc.

text: Then

text: ij

text: i

text: j

text: AA

text: A

text: A

text: AB

text: A

text: B

text: LL

text: ¯K(X

text: ¯K(X

text: X

text: ¯K(X

text: X

text: BA

text: BB

text: ¯K(X

text: X

text: ¯K(X

text: X

text: A

text: A

text: L

text: K(X

text: X)

text: K(X

text: X)

text: B

text: K(X

text: X)

text: L

text: A

text: A

text: B

text: B

text: ¯K(X,

text: X

text: ¯K(X,

text: X

text: ¯K(X,

text: X

text: Here

text: X

text: is

text: to

text: be

text: interpreted

text: as

text: a

text: set

text: of

text: points

text: at

text: which

text: we

text: evaluate

text: those

text: functions

text: drawn

text: A∪

text: B

text: from

text: the

text: posterior

text: distribution,

text: in

text: contrast

text: with

text: X

text: X

text: X

text: which

text: is

text: the

text: set

text: of

text: points

text: at

text: which

text: evaluations

text: of

text: the

text: forcing

text: terms

text: are

text: taken.

text: A

text: B

text: Proposition

text: (Probabilistic

text: Meshless

text: Method).

text: Assume

text: and

text: are

text: linear

text: operators.

text: Then

text: the

text: posterior

text: distribution

text: Πg,b

text: over

text: the

text: solution

text: of

text: the

text: PDE,

text: conditional

text: on

text: the

text: data

text: u

text: g,

text: b

text: is

text: such

text: that,

text: for

text: u

text: Πg,b

text: we

text: have

text: u

text: N

text: u(X)

text: (µ,

text: Σ)

text: L

text: LL

text: µ

text: ¯K(X,

text: X

text: ¯K(X

text: X

text: g

text: b

text: L

text: LL

text: L

text: Σ

text: K(X,

text: X)

text: ¯K(X,

text: X

text: ¯K(X

text: X

text: K(X

text: X)

text: Note

text: that

text: the

text: mean

text: function

text: in

text: Eq.

text: is

text: the

text: same

text: as

text: the

text: numerical

text: solution

text: to

text: the

text: PDE

text: that

text: would

text: be

text: obtained

text: using

text: the

text: method

text: of

text: symmetric

text: collocation

text: Thus

text: far

text: we

text: not

text: discussed

text: the

text: choice

text: of

text: prior

text: covariance

text: k.

text: There

text: are

text: several

text: inter-

text: esting

text: choices

text: in

text: the

text: literature.

text: Work

text: in

text: proposes

text: use

text: of

text: a

text: covariance

text: which

text: encodes

text: information

text: about

text: the

text: system

text: through

text: its

text: Green’s

text: function;

text: examined

text: the

text: properties

text: of

text: this

text: choice

text: in

text: more

text: detail.

text: However,

text: reliance

text: on

text: the

text: Green’s

text: function,

text: which

text: is

text: not

text: in

text: general

text: available

text: in

text: closed-form

text: for

text: complex

text: systems,

text: is

text: a

text: signiﬁcant

text: drawback.

text: In

text: practice

text: we

text: will

text: generally

text: posit

text: a

text: prior

text: covariance

text: directly

text: by

text: examining

text: the

text: system

text: in

text: question

text: and

text: selecting

text: a

text: prior

text: which

text: encodes

text: a

text: suitable

text: level

text: of

text: diﬀerentiability.


text: 10-1 10-1 10-2 10-2 10-3 10-3 10-4 10-5 10-4 0 20 40 60 80 100 0 20 40 60 80 100 mA mA Figure 2: Convergence of mean function (left) and posterior covariance trace (right) as the number of design points mA is increased. number of design points is increased are shown in Fig. 2 3 Application to Bayesian Inverse Problems We now turn to an examination of how the PMM, constructed in the previous section, can be applied in Bayesian inverse problems. We now have a system in which we assume A the operator depends upon some parameter θ, which we emphasise in the below system: A ∈ u(x) = g(x) x D θ B ∈ u(x) = b(x) x ∂D. ∼ In a Bayesian inverse problem we place a prior distribution over θ, θ Π , and seek to θ { } ⊂ determine its posterior distribution Πy based on data y collected at locations x D, θ i i = 1, . . . , n. Further details on Bayesian inverse problems can be found in [10]. Such a posterior distribution is usually intractable and must be investigated by sam- pling, which involves solution of the underlying system of PDEs as the sampler visits diﬀerent values of θ. We assume that the data is obtained by direct observation of the solution u at these locations, corrupted with Gaussian noise y = u(x ) + ξ i i i ∼ N where ξ (0, Γ). Our likelihood is thus given by | N p(y θ, u) = (y; u, Γ) (3) R where u, y are each vectors in n, with [u] = u(x ; θ) and [y] = y . i i i i Since the solution u to the PDE system is inaccessible it is common to replace u with an approximation uˆ obtained by some numerical scheme. We instead use the PMM as the forward solver, obtaining a measure Πg,b describing our uncertainty. We may them u 5 ku−µk )Σ(rT ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: default

text: mA

text: mA

text: Figure

text: Convergence

label: caption

text: of

text: mean

text: function

text: (left)

text: and

text: posterior

text: covariance

text: trace

text: (right)

text: as

text: the

text: number

text: of

text: design

text: points

text: mA

text: is

text: increased.

text: number

text: of

text: design

text: points

text: is

text: increased

text: are

text: shown

text: in

text: Fig.

text: Application

text: to

text: Bayesian

text: Inverse

text: Problems

text: We

text: now

text: turn

text: to

text: an

text: examination

text: of

text: how

text: the

text: PMM,

text: constructed

text: in

text: the

text: previous

text: section,

text: can

text: be

text: applied

text: in

text: Bayesian

text: inverse

text: problems.

text: We

text: now

text: have

text: a

text: system

text: in

text: which

text: we

text: assume

text: A

text: the

text: operator

text: depends

text: upon

text: some

text: parameter

text: θ,

text: which

text: we

text: emphasise

text: in

text: the

text: below

text: system:

text: A

text: u(x)

text: g(x)

text: x

text: D

text: θ

text: B

text: u(x)

text: b(x)

text: x

text: ∂D.

text: In

text: a

text: Bayesian

text: inverse

text: problem

text: we

text: place

text: a

text: prior

text: distribution

text: over

text: θ,

text: θ

text: Π

text: and

text: seek

text: to

text: θ

text: determine

text: its

text: posterior

text: distribution

text: Πy

text: based

text: on

text: data

text: y

text: collected

text: at

text: locations

text: x

text: D,

text: θ

text: i

text: i

text: n.

text: Further

text: details

text: on

text: Bayesian

text: inverse

text: problems

text: can

text: be

text: found

text: in

text: Such

text: a

text: posterior

text: distribution

text: is

text: usually

text: intractable

text: and

text: must

text: be

text: investigated

text: by

text: sam-

text: pling,

text: which

text: involves

text: solution

text: of

text: the

text: underlying

text: system

text: of

text: PDEs

text: as

text: the

text: sampler

text: visits

text: diﬀerent

text: values

text: of

text: θ.

text: We

text: assume

text: that

text: the

text: data

text: is

text: obtained

text: by

text: direct

text: observation

text: of

text: the

text: solution

text: u

text: at

text: these

text: locations,

text: corrupted

text: with

text: Gaussian

text: noise

text: y

text: u(x

text: ξ

text: i

text: i

text: i

text: N

text: where

text: ξ

text: Γ).

text: Our

text: likelihood

text: is

text: thus

text: given

text: by

text: N

text: p(y

text: θ,

text: u)

text: (y;

text: u,

text: Γ)

text: R

text: where

text: u,

text: y

text: are

text: each

text: vectors

text: in

text: n,

text: with

text: [u]

text: u(x

text: θ)

text: and

text: [y]

text: y

text: i

text: i

text: i

text: i

text: Since

text: the

text: solution

text: u

text: to

text: the

text: PDE

text: system

text: is

text: inaccessible

text: it

text: is

text: common

text: to

text: replace

text: u

text: with

text: an

text: approximation

text: uˆ

text: obtained

text: by

text: some

text: numerical

text: scheme.

text: We

text: instead

text: use

text: the

text: PMM

text: as

text: the

text: forward

text: solver,

text: obtaining

text: a

text: measure

text: Πg,b

text: describing

text: our

text: uncertainty.

text: We

text: may

text: them

text: u

text: ku−µk

text: )Σ(rT

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: MABUCHI METRICS AND RELATIVE DING STABILITY OF TORIC FANO VARIETIES 18 Firstly, we observe the following basic facts. Recall that a convex function g on (cid:52) ≥ is called normalized if g(y) g(0) = 0. I ≥ ≥ (cid:52) Proposition 12I. l(g) 0 for all convex(cid:90) function g if and only if l 0 on , and in this case (g) = 0 only when g is aﬃne. Moreover, there exists a constant l c > 0 such that I ≥ (g) c gdy l (cid:52) for all normalized convex function g if and only if inf(cid:52) l > 0. I Proof. By the deﬁnition of l, vanishes on aﬃne functions. By Jensen’s inequality ≥ (cid:52) I l ≥ (cid:82) (see ??), if l 0 on then (g) 0 for all convex g and the equality holds only when g is aﬃne. On the othelr hand, (cid:90)if (cid:52) (cid:42) {l ≥(cid:90) 0}, there exists convex g such I { } that (g) < 0. For example, take g = l+ = max 0, l , note that l2 = l(0), l I − − (cid:82) (l+) = l(0) + l2 = l2 < 0. l ≥ l 0 l<0 I ≥ For the second statement, if δ := inf(cid:52) l > 0, then (g) δ gdy for all normalized l convex function g. Conversely, if there exists a constant c > 0 such that the I ≥ ≥ (cid:52) inequality holds, we have (g) 0 for all convex(cid:90)g, thus l 0 on . If δ = 0, we { } l (cid:52) can take a sequence g of simple normalized convex functions on such that i { ≥ } ⊆ (cid:52) ∩ { ≤ } g 0 l 1/i , g = 1, (cid:82) i (cid:82) (cid:52) i { } where “simple” means that g = max 0, h for some aﬃne function h . ≤ I i · ≤ i → i (cid:3) Then c (g ) = { ≥ } g l 1 { ≥ } g = 1 0, it contradicts. l i gi 0 i i gi 0 i i Based on the above facts, we deﬁne the relative Ding stability as follows. ≥ (cid:52) Deﬁnition 13. Denote δ = inf(cid:52) l. If δ 0, we call is relative Ding stable. (cid:52) (cid:52) Otherwise δ < 0, we call is relative Ding unstable. Moreover, if δ > 0, we call is uniformly relative Ding stable. All these situations can happen, see the section of examples. In [Ma2], Mabuchi − de∈ﬁned an invariant αX := maxX pr(1 ehω), it is independent of the choice of ω 2πc (X). Obviously, if X admits Mabuchi metrics, then α < 1. In the toric 1 − |(cid:52)| X case, α = max(cid:52)(1 l). Thus the condition α < 1 is same to uniformly X X relative Ding stable in our terminology. (cid:52) Theorem 14. When X(cid:52) is an orbifold (this is equivalent to that is simplicial), (cid:52) X(cid:52) admits invariant Mabuchi metrics if and only if is uniformly relative Ding stable. Proof. Necessity is obvious by the above discussion. For the suﬃciency, we need to |(cid:52)| solve the equation eh(u) = l, m(cid:82)ore precisely − 1 · e u ∈ H det (uij) = R e−u l(∇u), u T , n ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: MABUCHI

text: METRICS

text: AND

text: RELATIVE

text: DING

text: STABILITY

text: OF

text: TORIC

text: FANO

text: VARIETIES

text: Firstly,

text: we

text: observe

text: the

text: following

text: basic

text: facts.

text: Recall

text: that

text: a

text: convex

text: function

text: g

text: on

text: is

text: called

text: normalized

text: if

text: g(y)

text: I

text: Proposition

text: l(g)

text: for

text: all

text: function

text: g

text: if

text: and

text: only

text: if

text: l

text: on

text: and

text: in

text: this

text: case

text: (g)

text: only

text: when

text: g

text: is

text: aﬃne.

text: Moreover,

text: there

text: exists

text: a

text: constant

text: l

text: c

text: such

text: that

text: I

text: (g)

text: c

text: gdy

text: l

text: for

text: all

text: normalized

text: convex

text: function

text: g

text: if

text: and

text: only

text: if

text: l

text: I

text: Proof.

text: By

text: the

text: deﬁnition

text: of

text: l,

text: vanishes

text: on

text: aﬃne

text: functions.

text: By

text: Jensen’s

text: inequality

text: I

text: l

text: (see

text: if

text: l

text: on

text: then

text: (g)

text: for

text: all

text: convex

text: g

text: and

text: the

text: equality

text: holds

text: only

text: when

text: g

text: is

text: aﬃne.

text: On

text: the

text: othelr

text: hand,

text: {l

text: there

text: exists

text: convex

text: g

text: such

text: I

text: that

text: (g)

text: For

text: example,

text: take

text: g

text: l+

text: max

text: l

text: note

text: that

text: l

text: I

text: (l+)

text: l

text: l

text: I

text: For

text: the

text: second

text: statement,

text: if

text: δ

text: l

text: then

text: (g)

text: δ

text: gdy

text: for

text: all

text: normalized

text: l

text: convex

text: function

text: g.

text: Conversely,

text: if

text: there

text: exists

text: a

text: constant

text: c

text: such

text: that

text: the

text: I

text: inequality

text: holds,

text: we

text: have

text: (g)

text: for

text: all

text: thus

text: l

text: on

text: If

text: δ

text: we

text: l

text: can

text: take

text: a

text: sequence

text: g

text: of

text: simple

text: normalized

text: convex

text: functions

text: on

text: such

text: that

text: i

text: g

text: l

text: g

text: i

text: i

text: where

text: “simple”

text: means

text: that

text: g

text: max

text: h

text: for

text: some

text: aﬃne

text: function

text: h

text: I

text: i

text: i

text: i

text: Then

text: c

text: (g

text: g

text: l

text: g

text: it

text: contradicts.

text: l

text: i

text: gi

text: i

text: i

text: gi

text: i

text: i

text: Based

text: on

text: the

text: above

text: facts,

text: we

text: deﬁne

text: the

text: relative

text: Ding

text: stability

text: as

text: follows.

text: Deﬁnition

text: Denote

text: δ

text: l.

text: If

text: δ

text: we

text: call

text: is

text: relative

text: Ding

text: stable.

text: Otherwise

text: δ

text: we

text: call

text: is

text: relative

text: Ding

text: unstable.

text: Moreover,

text: if

text: δ

text: we

text: call

text: is

text: uniformly

text: relative

text: Ding

text: stable.

text: All

text: these

text: situations

text: can

text: happen,

text: see

text: the

text: section

text: of

text: examples.

text: In

text: Mabuchi

text: de∈ﬁned

text: an

text: invariant

text: αX

text: maxX

text: ehω),

text: it

text: is

text: independent

text: of

text: the

text: choice

text: of

text: ω

text: (X).

text: Obviously,

text: if

text: X

text: admits

text: Mabuchi

text: metrics,

text: then

text: α

text: In

text: the

text: toric

text: X

text: case,

text: α

text: l).

text: Thus

text: the

text: condition

text: α

text: is

text: same

text: to

text: uniformly

text: X

text: X

text: relative

text: Ding

text: stable

text: in

text: our

text: terminology.

text: Theorem

text: When

text: is

text: an

text: orbifold

text: (this

text: is

text: equivalent

text: to

text: that

text: is

text: simplicial),

text: admits

text: invariant

text: Mabuchi

text: metrics

text: if

text: and

text: only

text: if

text: is

text: uniformly

text: relative

text: Ding

text: stable.

text: Proof.

text: Necessity

text: is

text: obvious

text: by

text: the

text: above

text: discussion.

text: For

text: the

text: suﬃciency,

text: we

text: need

text: to

text: solve

text: the

text: equation

text: eh(u)

text: l,

text: precisely

text: e

text: u

text: H

text: det

text: (uij)

text: R

text: e−u

text: l(∇u),

text: u

text: T

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Symbol Meaning In principle, an optimal algorithm requires O(1) space [10], (cid:15) and runs in constant time. The algorithm provides an approx- R The total sum of all items in the stream so far. imation guarantee that the error is bounded by R(cid:15) where R is (cid:6) (cid:7) Rt The total sum of all items in the stream until time t. the total weight of all ﬂows in the stream. Intuitively, our periodic maintenance process identiﬁes the fx The weighted frequency for item x in the stream so far. 1 th largest counter, and evicts all ﬂows whose counters f(cid:98)xt The weighted frequency for item x, at time t. is(cid:15) smaller than that counter. This is obtained by internally ft An estimate of the weighted frequency of item x, at time t. splitting the table into two sub-tables named Active and x Passive. Each table entry contains both the ﬂow’s id and a A speed-space tradeoff parameter, affects frequency of γ counter that represents the ﬂow’s volume. The Active table is maintenance operations and memory consumption. mutable, while the Passive is read-only. That is, updates only (cid:15) Accuracy parameter, small (cid:15)(cid:108)mean(cid:109)s lower estimation error affect the Active table w(cid:6)hil(cid:7)e queries consider both of them. but more counters. The maintenance process copies all counters that are larger qt The estimate of the top 1+1γ quantile at time t. than the quantile of the 1 th largest ﬂow from the Passive (cid:15) (cid:6) (cid:7) θ Threshold for elephant ﬂows. table to the Active table, clears the Passive table, and then switches between them. That way, the size of the Active and δ The error probability allowed in randomized algorithms. (cid:6) (cid:7) (cid:6) (cid:7) Passive tables remains bounded while the 1 largest ﬂows (cid:15) Table II: Summary of notations used in this paper. are never evicted. (cid:44) − Each table is conﬁgured to store at most: T γ + 1 1 (cid:15) (cid:15) items, where γ is a positive constant that affects a speed-space A. Problem deﬁnitions: trade off as explained below. In addition, we keep a single ﬂoating point variable q, which represents the value of the We now formally deﬁne the problems we address. last quantile calculated. q is the default estimation returned • (cid:15) - VOLUME ESTIMATION: We say tha(cid:98)t an algorithm when querying the frequency of non-resident ﬂows. It ensures solves the (cid:15) - VOLUME ESTIMATION problem if at any that such estimates meet the maximum error guarantee. time t, Query(x) retur(cid:98)ns an estimation fxt that satisﬁes We then improve the complexity to worst case O(1) with a ≤ ≤ · de-amortization process. Intuitively, this is done by performing ft ft ft + R (cid:15). x x x t a small piece of the maintenance prior to each update. We need • (θ, (cid:15))-ELEPHANT FLOWS: We say that an algorithm to make sure that maintenance is always ﬁnished by the time solves the (θ, (cid:15)) - ELEPHANT FLOWS problem if at any the Active table ﬁlls up. Once maintenance is over, we switch time t, an Elephants() query returns a set of elements the Active table with the (now empty) Passive table. · ⇒ ∈ S , such that for every ﬂow x, ft > R θ = x S , t · − ⇒ (cid:54)∈x t t and ft < R (θ (cid:15)) = x S . We note that if the B. Iterative Median Summing x t t stream is unweighted (all weights are 1), this degenerates We describe our Iterative Median SUMming (IM-SUM) to the Heavy Hitters problem discussed in [14], [37], [45]. algorithm and its deamortized variant Deamortized Iterative Median SUMming (DIM-SUM), by detailing four operations: a query operation, which computes the volume of a ﬂow; an elephants method that returns all elephant ﬂows; an update op- B. Notations eration, which increases the volume of a ﬂow corresponding to a recently arrived packet; and a maintenance operation, which The notations used in this paper are summarized in Table II. periodically discards infrequent ﬂows to prevent overﬂowing. III. SOLUTION (cid:98) a) Query(x): The query procedure appears in Figure 1. As depicted, the estimated weighted frequency of element x, A. Intuition ((f ), is Active[x] if x has an Active table entry, Passive[x] x Ideally, when the table is full, we wish to evict the smallest if x has a Passive table entry and otherwise q. ﬂow as in Space Saving. However, in the weighted case, Space b) ←Ele∅phants(): Returns the elephant ﬂows. First, we Saving runs in logarithmic time. We achieve constant runtime set St ; then, we traverse both the Active and≥Passi·ve by relaxing the memory constraint; instead of removing the tables, adding to St any ﬂow x for which Query(x) Rt θ. c) Update: The update procedure is illustrated in Fig- minimal ﬂow upon arrival of a non resident ﬂow, we peri- odically remove many small ﬂows from the table at once. ure 2. The procedure deals with an arrival of a pair (ai, w) This maintenance operation takes linear time, but it is invoked (ﬂow id, weight), e.g., ai (cid:98)may be a TCP ﬁ(cid:16)ve tuple and(cid:17)w infrequently enough to achieve amortized O(1) runtime. The the byte size of its payload. I−n the update procedu(cid:98)re, we ﬁrst table size only increases by a constant factor, so our solution perform a query for ai. Let fati 1 be the query result−for ai. We remains (asymptotically) space optimal. add the following entry to the Active table: a , ft 1 + w . i ai ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Symbol

label: table

text: Meaning

text: In

text: principle,

text: an

text: optimal

text: algorithm

text: requires

text: space

text: and

text: runs

text: in

text: constant

text: time.

text: The

text: algorithm

text: provides

text: an

text: approx-

text: R

text: The

text: total

text: sum

text: of

text: all

text: items

text: in

text: the

text: stream

text: so

text: far.

text: imation

text: guarantee

text: that

text: the

text: error

text: is

text: bounded

text: by

text: where

text: R

text: is

text: Rt

text: The

text: total

text: sum

text: of

text: all

text: items

text: in

text: the

text: stream

text: until

text: time

text: t.

text: the

text: total

text: weight

text: of

text: all

text: ﬂows

text: in

text: the

text: stream.

text: Intuitively,

text: our

text: periodic

text: maintenance

text: process

text: identiﬁes

text: the

text: fx

text: The

text: weighted

text: frequency

text: for

text: item

text: x

text: in

text: the

text: stream

text: so

text: far.

text: th

text: largest

text: counter,

text: and

text: evicts

text: all

text: ﬂows

text: whose

text: counters

text: The

text: weighted

text: frequency

text: for

text: item

text: x,

text: at

text: time

text: t.

text: smaller

text: than

text: that

text: counter.

text: This

text: is

text: obtained

text: by

text: internally

text: ft

text: An

text: estimate

text: of

text: the

text: weighted

text: frequency

text: of

text: item

text: x,

text: at

text: time

text: t.

text: splitting

text: the

text: table

text: into

text: two

text: sub-tables

text: named

text: Active

text: and

text: x

text: Passive.

text: Each

text: table

text: entry

text: contains

text: both

text: the

text: ﬂow’s

text: id

text: and

text: a

text: A

text: speed-space

text: tradeoff

text: parameter,

text: affects

text: frequency

text: of

text: γ

text: counter

text: that

text: represents

text: the

text: ﬂow’s

text: volume.

text: The

text: Active

text: table

text: is

text: maintenance

text: operations

text: and

text: memory

text: consumption.

text: mutable,

text: while

text: the

text: Passive

text: is

text: read-only.

text: That

text: is,

text: updates

text: only

text: Accuracy

text: parameter,

text: small

text: lower

text: estimation

text: error

text: affect

text: the

text: Active

text: table

text: queries

text: consider

text: both

text: of

text: them.

text: but

text: more

text: counters.

text: The

text: maintenance

text: process

text: copies

text: all

text: counters

text: that

text: are

text: larger

text: qt

text: The

text: estimate

text: of

text: the

text: top

text: quantile

text: at

text: time

text: t.

text: than

text: the

text: quantile

text: of

text: the

text: th

text: largest

text: ﬂow

text: from

text: the

text: Passive

text: θ

text: Threshold

text: for

text: elephant

text: ﬂows.

text: table

text: to

text: the

text: Active

text: table,

text: clears

text: the

text: Passive

text: table,

text: and

text: then

text: switches

text: between

text: them.

text: That

text: way,

text: the

text: size

text: of

text: the

text: Active

text: and

text: δ

text: The

text: error

text: probability

text: allowed

text: in

text: randomized

text: algorithms.

text: Passive

text: tables

text: remains

text: bounded

text: while

text: the

text: largest

text: ﬂows

text: Table

text: II:

text: Summary

text: of

text: notations

text: used

text: in

text: this

text: paper.

text: are

text: never

text: evicted.

text: Each

text: table

text: is

text: conﬁgured

text: to

text: store

text: at

text: most:

text: T

text: γ

text: items,

text: where

text: γ

text: is

text: a

text: positive

text: constant

text: that

text: affects

text: a

text: speed-space

text: A.

text: Problem

text: deﬁnitions:

text: trade

text: off

text: as

text: explained

text: below.

text: In

text: addition,

text: we

text: keep

text: a

text: single

text: ﬂoating

text: point

text: variable

text: q,

text: which

text: represents

text: the

text: value

text: of

text: the

text: We

text: now

text: formally

text: deﬁne

text: the

text: problems

text: we

text: address.

text: last

text: quantile

text: calculated.

text: q

text: is

text: the

text: default

text: estimation

text: returned

text: VOLUME

text: ESTIMATION:

text: We

text: say

text: an

text: algorithm

text: when

text: querying

text: the

text: frequency

text: of

text: non-resident

text: ﬂows.

text: It

text: ensures

text: solves

text: the

text: VOLUME

text: ESTIMATION

text: problem

text: if

text: at

text: any

text: that

text: such

text: estimates

text: meet

text: the

text: maximum

text: error

text: guarantee.

text: time

text: t,

text: Query(x)

text: an

text: estimation

text: fxt

text: that

text: satisﬁes

text: We

text: then

text: improve

text: the

text: complexity

text: to

text: worst

text: case

text: with

text: a

text: de-amortization

text: process.

text: Intuitively,

text: this

text: is

text: done

text: by

text: performing

text: ft

text: ft

text: ft

text: R

text: x

text: x

text: x

text: t

text: a

text: small

text: piece

text: of

text: the

text: maintenance

text: prior

text: to

text: each

text: update.

text: We

text: need

text: (θ,

text: FLOWS:

text: We

text: say

text: that

text: an

text: algorithm

text: to

text: make

text: sure

text: that

text: maintenance

text: is

text: always

text: ﬁnished

text: by

text: the

text: time

text: solves

text: the

text: (θ,

text: ELEPHANT

text: FLOWS

text: problem

text: if

text: at

text: any

text: the

text: Active

text: table

text: ﬁlls

text: up.

text: Once

text: maintenance

text: is

text: over,

text: we

text: switch

text: time

text: t,

text: an

text: Elephants()

text: query

text: returns

text: a

text: set

text: of

text: elements

text: the

text: Active

text: table

text: with

text: the

text: (now

text: empty)

text: Passive

text: table.

text: S

text: such

text: that

text: for

text: every

text: ﬂow

text: x,

text: ft

text: R

text: θ

text: x

text: S

text: t

text: t

text: t

text: and

text: ft

text: R

text: (θ

text: x

text: S

text: We

text: note

text: that

text: if

text: the

text: B.

text: Iterative

text: Median

text: Summing

text: x

text: t

text: t

text: stream

text: is

text: unweighted

text: (all

text: weights

text: are

text: this

text: degenerates

text: We

text: describe

text: our

text: Iterative

text: Median

text: SUMming

text: (IM-SUM)

text: to

text: the

text: Heavy

text: Hitters

text: problem

text: discussed

text: in

text: algorithm

text: and

text: its

text: deamortized

text: variant

text: Deamortized

text: Iterative

text: Median

text: SUMming

text: (DIM-SUM),

text: by

text: detailing

text: four

text: operations:

text: a

text: query

text: operation,

text: which

text: computes

text: the

text: volume

text: of

text: a

text: ﬂow;

text: an

text: elephants

text: method

text: that

text: returns

text: all

text: elephant

text: ﬂows;

text: an

text: update

text: op-

text: B.

text: Notations

text: eration,

text: which

text: increases

text: the

text: volume

text: of

text: a

text: ﬂow

text: corresponding

text: to

text: a

text: recently

text: arrived

text: packet;

text: and

text: a

text: maintenance

text: operation,

text: which

text: The

text: notations

text: used

text: in

text: this

text: paper

text: are

text: summarized

text: in

text: Table

text: II.

text: periodically

text: discards

text: infrequent

text: ﬂows

text: to

text: prevent

text: overﬂowing.

text: III.

text: SOLUTION

text: a)

text: Query(x):

text: The

text: query

text: procedure

text: appears

text: in

text: Figure

text: As

text: depicted,

text: the

text: estimated

text: weighted

text: frequency

text: of

text: element

text: x,

text: A.

text: Intuition

text: ((f

text: is

text: Active[x]

text: if

text: x

text: has

text: an

text: Active

text: table

text: entry,

text: Passive[x]

text: x

text: Ideally,

text: when

text: the

text: table

text: is

text: full,

text: we

text: wish

text: to

text: evict

text: the

text: smallest

text: if

text: x

text: has

text: a

text: Passive

text: table

text: entry

text: and

text: otherwise

text: q.

text: ﬂow

text: as

text: in

text: Space

text: Saving.

text: However,

text: in

text: the

text: weighted

text: case,

text: Space

text: b)

text: ←Ele∅phants():

text: Returns

text: the

text: elephant

text: ﬂows.

text: First,

text: we

text: Saving

text: runs

text: in

text: logarithmic

text: time.

text: We

text: achieve

text: constant

text: runtime

text: set

text: St

text: then,

text: we

text: traverse

text: both

text: the

text: Active

text: and≥Passi·ve

text: by

text: relaxing

text: the

text: memory

text: constraint;

text: instead

text: of

text: removing

text: the

text: tables,

text: adding

text: to

text: St

text: any

text: ﬂow

text: x

text: for

text: which

text: Query(x)

text: Rt

text: θ.

text: c)

text: Update:

text: The

text: update

text: procedure

text: is

text: illustrated

text: in

text: Fig-

text: minimal

text: ﬂow

text: upon

text: arrival

text: of

text: a

text: non

text: resident

text: ﬂow,

text: we

text: peri-

text: odically

text: remove

text: many

text: small

text: ﬂows

text: from

text: the

text: table

text: at

text: once.

text: ure

text: The

text: procedure

text: deals

text: with

text: an

text: arrival

text: of

text: a

text: pair

text: (ai,

text: w)

text: This

text: maintenance

text: operation

text: takes

text: linear

text: time,

text: but

text: it

text: is

text: invoked

text: (ﬂow

text: id,

text: weight),

text: e.g.,

text: ai

text: be

text: a

text: TCP

text: tuple

text: infrequently

text: enough

text: to

text: achieve

text: amortized

text: runtime.

text: The

text: the

text: byte

text: size

text: of

text: its

text: payload.

text: I−n

text: the

text: update

text: we

text: ﬁrst

text: table

text: size

text: only

text: increases

text: by

text: a

text: constant

text: factor,

text: so

text: our

text: solution

text: perform

text: a

text: query

text: for

text: ai.

text: Let

text: fati

text: be

text: the

text: query

text: result−for

text: ai.

text: We

text: remains

text: (asymptotically)

text: space

text: optimal.

text: add

text: the

text: following

text: entry

text: to

text: the

text: Active

text: table:

text: a

text: ft

text: w

text: i

text: ai

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:16) (cid:17) ≤ − − iotnemlysgfrroowms tdhueePt(cid:18)oas(cid:24)usipvd(cid:25)eatteabol(cid:19)pe.erOattihoenrst.hTahnetrheafot,reth,ethAercetivmeutsatbblee MThterdeefcorreea,stehsetnouamtbmerosotfM(cid:16)mta+in1ten(cid:17)aMncte opMUetrtat=ionMstex1ecuteU1dt at. (cid:18) (cid:19) (cid:18) (cid:19) at least time t + 1 is   Gmin = T − (cid:108)1(cid:15) (cid:109)− 1(cid:24) (cid:25) (cid:18)(cid:24) (cid:25) (cid:19) (cid:108) (cid:109) O Mt+1 ≤ O Mt 1−− U1t = O Mt = O(1). U U 1 U γ 1 − − 1 − γ t+1 t t = + 1 1 = (cid:15) (cid:15) (cid:15) (cid:15) The query process requires 2 hash table operations and is updates in each generation. therefore also O(1). Next, we bound the number of hash table operations re- quired to perform the maintenance process. (cid:0) (cid:1) C. Required Space Lemma 3. The maintenance process requires: M = O 1+γ We now show that for each constant γ, IM-SUM and DIM- hash table operations. (cid:15) SUM require the (asymptotically) optimal O(1) table entries. (cid:15) Theorem 4. For each constant γ, the space complexity of Proof. We calculate the complexity of all steps. For Step 1, it IM-SUM and DIM-SUM is O(1). ε is well known that a median can be found in linear time, e.g., using the median of median(cid:18)s algori(cid:19)thm. The same is true for any percentile, and therefore Step 1 requires Proof. The proof follows from the selected table sizes. Each table is sized to contain a maximum of γ + 1 entries and 1 + γ (cid:15) (cid:15) O therefore the total number of table entries is O(1). (cid:15) (cid:0) (cid:1) (cid:15) hash table operations to complete. (cid:0) (cid:1) Step 2 goes over the Passive table, which is of size O 1+(cid:15)γ , V. EVALUATION and copies or moves some of the items to the Active table. We now present an extensive evaluation for comparing our Therefore, its complexity is O 1+γ . (cid:15) proposed algorithm with the leading alternatives. We only Step 3 can be perform(cid:18)ed in O(cid:19)(1) and so does Step 4. considered alternative algorithms that are able to count packets Therefore, the total complexity of all steps is: of variable sizes and are able to answer queries on-line. 1 + γ O . (cid:15) A. Datasets Our evaluation includes the following datasets: 1) The CAIDA Chicago Anonymized Internet Trace 2015 [2] , denoted Chicago. The trace was collected by Theorem 3. For any ﬁxed γ, IM-SUM runs in O(1) amortized the ‘equinix-chicago’ high-speed monitor and contains a and DIM-SUM in O(1) worst case hash table operations. mix of 6.3M TCP, UDP and ICMP packets. The weight of each packed is deﬁned as the size of its payload, not including the header. Proof. First, we observe that for any constant γ, Lemma 2 2) The CAIDA San Jose Anonymized Internet Trace establishes that there are O(1) update operations between 2014 [3] , denoted SanJose. The trace was collected by (cid:15) generations. Similarly, by Lemma 3, there are O(1) hash the ‘equinix-sanjose’ high-speed monitor and contains a (cid:15) function operations to do during each maintenance process. mix of 20.2M TCP, UDP and ICMP packets. The weight In IM-SUM, maintenance is performed once per generation of each packet is deﬁned as the size of its payload, not and thus the amortized complexity is O(1). including the header. In DIM-SUM, as the work is split between update opera- 3) The UCLA Computer Science department TCP packet tions, each update has to perform O(1) hash table operations. trace (denoted UCLA-TCP) [4]. This trace contains Let U be the minimum number of update operations left in 16.5M TCP packets passed through the border router t the generation at time t and let M be the maximum number of the Computer Science Department, University of t of maintenance operations left. We show by induction that California, Los Angeles. The weight of each packet is Mt = O(1). At a t in the beginning of the generation, deﬁned as the size of its payload, not including the Ut UtA=ssGummein, baynidndMuctt=ionM, th. aTthfoerreafnoyret,imMUettt=, MOt(=1).O(1). After 4) hUeCadLeAr-.UDP [4]. This trace contains 18.5M UDP pack- a single update, U ≥ U − 1, because otUhterwise the min- ets passed through the border router of the Computer t+1 t imum number of updates at time t would be smaller than U . Science Department, UCLA. The weight of each packet t ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: iotnemlysgfrroowms

text: at.

text: at

text: least

text: time

text: t

text: is

text: Gmin

text: T

text: O

text: O

text: Mt

text: 1−−

text: O

text: Mt

text: U

text: U

text: U

text: γ

text: γ

text: t

text: t

text: The

text: query

text: process

text: requires

text: hash

text: table

text: operations

text: and

text: is

text: updates

text: in

text: each

text: generation.

text: therefore

text: also

text: Next,

text: we

text: bound

text: the

text: number

text: of

text: hash

text: table

text: operations

text: re-

text: quired

text: to

text: perform

text: the

text: maintenance

text: process.

text: C.

text: Required

text: Space

text: Lemma

text: The

text: maintenance

text: process

text: requires:

text: M

text: O

text: We

text: now

text: show

text: that

text: for

text: each

text: constant

text: γ,

text: IM-SUM

text: and

text: DIM-

text: hash

text: table

text: operations.

text: SUM

text: require

text: the

text: (asymptotically)

text: optimal

text: table

text: entries.

text: Theorem

text: For

text: each

text: constant

text: γ,

text: the

text: space

text: complexity

text: of

text: Proof.

text: We

text: calculate

text: the

text: complexity

text: of

text: all

text: steps.

text: For

text: Step

text: it

text: IM-SUM

text: and

text: DIM-SUM

text: is

text: ε

text: is

text: well

text: known

text: that

text: a

text: median

text: can

text: be

text: found

text: in

text: linear

text: time,

text: e.g.,

text: using

text: the

text: median

text: of

text: The

text: same

text: is

text: true

text: for

text: any

text: percentile,

text: and

text: therefore

text: Step

text: requires

text: Proof.

text: The

text: proof

text: follows

text: from

text: the

text: selected

text: table

text: sizes.

text: Each

text: table

text: is

text: sized

text: to

text: contain

text: a

text: maximum

text: of

text: γ

text: entries

text: and

text: γ

text: O

text: therefore

text: the

text: total

text: number

text: of

text: table

text: entries

text: is

text: hash

text: table

text: operations

text: to

text: complete.

text: Step

text: goes

text: over

text: the

text: Passive

text: table,

text: which

text: is

text: of

text: size

text: O

text: V.

text: EVALUATION

text: and

text: copies

text: or

text: moves

text: some

text: of

text: the

text: items

text: to

text: the

text: Active

text: table.

text: We

text: now

text: present

text: an

text: extensive

text: evaluation

text: for

text: comparing

text: our

text: Therefore,

text: its

text: complexity

text: is

text: O

text: proposed

text: algorithm

text: with

text: the

text: leading

text: alternatives.

text: We

text: only

text: Step

text: can

text: be

text: in

text: and

text: so

text: does

text: Step

text: considered

text: alternative

text: algorithms

text: that

text: are

text: able

text: to

text: count

text: packets

text: Therefore,

text: the

text: total

text: complexity

text: of

text: all

text: steps

text: is:

text: of

text: variable

text: sizes

text: and

text: are

text: able

text: to

text: answer

text: queries

text: on-line.

text: γ

text: O

text: A.

text: Datasets

text: Our

text: evaluation

text: includes

text: the

text: following

text: datasets:

text: The

text: CAIDA

text: Chicago

text: Anonymized

text: Internet

text: Trace

text: denoted

text: Chicago.

text: The

text: trace

text: was

text: collected

text: by

text: Theorem

text: For

text: any

text: ﬁxed

text: γ,

text: IM-SUM

text: runs

text: in

text: amortized

text: the

text: ‘equinix-chicago’

text: high-speed

text: monitor

text: and

text: contains

text: a

text: and

text: DIM-SUM

text: in

text: worst

text: case

text: hash

text: table

text: operations.

text: mix

text: of

text: TCP,

text: UDP

text: and

text: ICMP

text: packets.

text: The

text: weight

text: of

text: each

text: packed

text: is

text: deﬁned

text: as

text: the

text: size

text: of

text: its

text: payload,

text: not

text: including

text: the

text: header.

text: Proof.

text: First,

text: we

text: observe

text: that

text: for

text: any

text: constant

text: γ,

text: Lemma

text: The

text: CAIDA

text: San

text: Jose

text: Anonymized

text: Internet

text: Trace

text: establishes

text: that

text: there

text: are

text: update

text: operations

text: between

text: denoted

text: SanJose.

text: The

text: trace

text: was

text: collected

text: by

text: generations.

text: Similarly,

text: by

text: Lemma

text: there

text: are

text: hash

text: the

text: ‘equinix-sanjose’

text: high-speed

text: monitor

text: and

text: contains

text: a

text: function

text: operations

text: to

text: do

text: during

text: each

text: maintenance

text: process.

text: mix

text: of

text: TCP,

text: UDP

text: and

text: ICMP

text: packets.

text: The

text: weight

text: In

text: IM-SUM,

text: maintenance

text: is

text: performed

text: once

text: per

text: generation

text: of

text: each

text: packet

text: is

text: deﬁned

text: as

text: the

text: size

text: of

text: its

text: payload,

text: not

text: and

text: thus

text: the

text: amortized

text: complexity

text: is

text: including

text: the

text: header.

text: In

text: DIM-SUM,

text: as

text: the

text: work

text: is

text: split

text: between

text: update

text: opera-

text: The

text: UCLA

text: Computer

text: Science

text: department

text: TCP

text: packet

text: tions,

text: each

text: update

text: has

text: to

text: perform

text: hash

text: table

text: operations.

text: trace

text: (denoted

text: UCLA-TCP)

text: This

text: trace

text: contains

text: Let

text: U

text: be

text: the

text: minimum

text: number

text: of

text: update

text: operations

text: left

text: in

text: TCP

text: packets

text: passed

text: through

text: the

text: border

text: router

text: t

text: the

text: generation

text: at

text: time

text: t

text: and

text: let

text: M

text: be

text: the

text: maximum

text: number

text: of

text: the

text: Computer

text: Science

text: Department,

text: University

text: of

text: t

text: of

text: maintenance

text: operations

text: left.

text: We

text: show

text: by

text: induction

text: that

text: California,

text: Los

text: Angeles.

text: The

text: weight

text: of

text: each

text: packet

text: is

text: Mt

text: At

text: a

text: t

text: in

text: the

text: beginning

text: of

text: the

text: generation,

text: deﬁned

text: as

text: the

text: size

text: of

text: its

text: payload,

text: not

text: including

text: the

text: Ut

text: UtA=ssGummein,

text: baynidndMuctt=ionM,

text: th.

text: aTthfoerreafnoyret,imMUettt=,

text: After

text: hUeCadLeAr-.UDP

text: This

text: trace

text: contains

text: UDP

text: pack-

text: a

text: single

text: update,

text: U

text: U

text: because

text: otUhterwise

text: the

text: min-

text: ets

text: passed

text: through

text: the

text: border

text: router

text: of

text: the

text: Computer

text: t

text: imum

text: number

text: of

text: updates

text: at

text: time

text: t

text: would

text: be

text: smaller

text: than

text: U

text: Science

text: Department,

text: UCLA.

text: The

text: weight

text: of

text: each

text: packet

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##