text: Remark 5.4: We ran experiments for small values of d and n, summarised ≤ in Table 3. They show that the smallest D such that χ(D) D is equal to the smallest D such that the XL algorithm terminates, i.e. the lower bound was met in all (but one, see next Remark) of our experiments. Remark 5.5: In one experiment, namely p = 3109, d = 2, n = 6, the reader will notice that D = 6.99 and not 7. This means that 1 out average of 100 randomly chosen sets of input polynomials ﬁnished with D = 6 and not D = 7. We then checked this particular set of input polynomials, and two coeﬃcients were equal in one polynomial, i.e., the polynomials were not generic in this one case. This is an example that shows that our bound is (conjecturally) tight for generic polynomials, but non-generic polynomials may ﬁnish with a smaller D. ∗ Let us denote by D the optimal input value of D in the XL algorithm, ∗ i.e., D is the smallest D such that the XL algorithm succeeds. Based on the evidence in Table 3 we conjecture that our lower bound in Corollary 5.1 is tight for generic polynomials. Conjecture 5.6: When c = 1 and the polynomials are generic we have ∗ − − D = (d 1)(n + 1) 1. ∗ Remark 5.7: In the notation of Remark 3.10 we are conjecturing that D = D = D . χ m √ Remark 5.8: Our conjecture is consistent with Proposition 6 in [Die04] ≥ − where it is shown that D n/(1 + c 1) for quadratic equations. When ≥χ ∗ c = 1 this becomes D n, and our conjecture with d = 2 becomes D = n. χ Remark 5.9: When the equations do not all have the same degree, we can take d to be the maximum of the degrees and the above arguments will give a good starting input value for D, but not necessarily the optimal value. 6 Two more equations than unknowns (c = 2) in XL When c > 1 (c being t(cid:18)he diﬀe(cid:19)rence between(cid:18)the num(cid:19)ber of equations and the number of unknowns), then Theorem 3.8 tells us that ≥ n + 1 − − n + 1 χ(D) (c 1) − D − D d − d 1 d 1 (cid:0) (cid:1) (cid:0) (cid:1) when we have n unknowns, and all equations have the same degree d. When c = 2 we need the following result. − ≤ Theorem 6.1: The smallest k such that N −N k is k s k (s+1) s 13 ##LTLine##

text: Remark

text: We

text: ran

text: experiments

text: for

text: small

text: values

text: of

text: d

text: and

text: n,

text: summarised

text: in

text: Table

text: They

text: show

text: that

text: the

text: smallest

text: D

text: such

text: that

text: χ(D)

text: D

text: is

text: equal

text: to

text: the

text: smallest

text: D

text: such

text: that

text: the

text: XL

text: algorithm

text: terminates,

text: i.e.

text: the

text: lower

text: bound

text: was

text: met

text: in

text: all

text: (but

text: one,

text: see

text: next

text: Remark)

text: of

text: our

text: experiments.

text: Remark

text: In

text: one

text: experiment,

text: namely

text: p

text: d

text: n

text: the

text: reader

text: will

text: notice

text: that

text: D

text: and

text: not

text: This

text: means

text: that

text: out

text: average

text: of

text: randomly

text: chosen

text: sets

text: of

text: input

text: polynomials

text: ﬁnished

text: with

text: D

text: and

text: not

text: D

text: We

text: then

text: checked

text: this

text: particular

text: set

text: of

text: input

text: polynomials,

text: and

text: two

text: coeﬃcients

text: were

text: equal

text: in

text: one

text: polynomial,

text: i.e.,

text: the

text: polynomials

text: were

text: not

text: generic

text: in

text: this

text: one

text: case.

text: This

text: is

text: an

text: example

text: that

text: shows

text: that

text: our

text: bound

text: is

text: (conjecturally)

text: tight

text: for

text: generic

text: polynomials,

text: but

text: non-generic

text: polynomials

text: may

text: ﬁnish

text: with

text: a

text: smaller

text: D.

text: Let

text: us

text: denote

text: by

text: D

text: the

text: optimal

text: input

text: value

text: of

text: D

text: in

text: the

text: XL

text: algorithm,

text: i.e.,

text: D

text: is

text: the

text: smallest

text: D

text: such

text: that

text: the

text: XL

text: algorithm

text: succeeds.

text: Based

text: on

text: the

text: evidence

text: in

text: Table

text: we

text: conjecture

text: that

text: our

text: lower

text: bound

text: in

text: Corollary

text: is

text: tight

text: for

text: generic

text: polynomials.

text: Conjecture

text: When

text: c

text: and

text: the

text: polynomials

text: are

text: generic

text: we

text: have

text: D

text: (d

text: Remark

text: In

text: the

text: notation

text: of

text: Remark

text: we

text: are

text: conjecturing

text: that

text: D

text: D

text: D

text: χ

text: m

text: Remark

text: Our

text: conjecture

text: is

text: consistent

text: with

text: Proposition

text: in

text: where

text: it

text: is

text: shown

text: that

text: D

text: c

text: for

text: quadratic

text: equations.

text: When

text: ≥χ

text: c

text: this

text: becomes

text: D

text: n,

text: and

text: our

text: conjecture

text: with

text: d

text: becomes

text: D

text: n.

text: χ

text: Remark

text: When

text: the

text: equations

text: do

text: not

text: all

text: have

text: the

text: same

text: degree,

text: we

text: can

text: take

text: d

text: to

text: be

text: the

text: maximum

text: of

text: the

text: degrees

text: and

text: the

text: above

text: arguments

text: will

text: give

text: a

text: good

text: starting

text: input

text: value

text: for

text: D,

text: but

text: not

text: necessarily

text: the

text: optimal

text: value.

text: Two

text: more

text: equations

text: than

text: unknowns

text: (c

text: in

text: XL

text: When

text: c

text: (c

text: being

text: of

text: equations

text: and

text: the

text: number

text: of

text: unknowns),

text: then

text: Theorem

text: tells

text: us

text: that

text: n

text: n

text: χ(D)

text: (c

text: D

text: D

text: d

text: d

text: d

text: when

text: we

text: have

text: n

text: unknowns,

text: and

text: all

text: equations

text: have

text: the

text: same

text: degree

text: d.

text: When

text: c

text: we

text: need

text: the

text: following

text: result.

text: Theorem

text: The

text: smallest

text: k

text: such

text: that

text: N

text: −N

text: k

text: is

text: k

text: s

text: k

text: s

text: ##LTLine##


text: (a) k = s + 1 for N = 2, (b) k = 2s for N = 3, (cid:98) (cid:99) ≥ (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) (c) k = s(N+1) + 1 for N 4. (cid:0) (cid:1)2 (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) ≤ − − Proof: (a) N = 2: If k s then 2 4=.1(cid:0)0 2(cid:1)+k 1(cid:0) = k + 1(cid:1), and thus 2 − ∀ ≤k s k − k s − 2 = k+1 0 > k k s. Now 2 sy=m. −2 4=.10 2+−s 2 = s k (s+1) s (cid:18) (cid:19) (cid:18) s+−1 s (cid:19) s 1 s (cid:18)− s ≤1 (cid:19) since we have a peak at s, and thus 2 −2 (cid:88)= s 1 s+1. s+1 s s+1 (s+1) s (cid:18) (cid:19) ≤ 3 − 3 k 2 − (b) N = 3: If k s then − 4=.6 − k k (s + 1) k m s s m=0 s ≥ 2 0 > k by part (a) and since the ordinary multinomials are (cid:18)k (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) s ≤ ≤ ≤ nonnegative. Now let k = s + t where 1 t s, i.e. s < k 2s. Thus 3 − (cid:18) 3 (cid:19) 3 (cid:18) − 3 (cid:19) (cid:88)− = (cid:88) − k k (s + 1) s + t t 1 s s s s − s 2 − t 1 2 4=.6 (cid:88) (cid:18) − (cid:19) (cid:88) (cid:18) − − (cid:19) (cid:88) (cid:18) (cid:19) s + t m t 1 m m=0 s m=0 s − − t 1 2 s 2 − t 1 2 (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) = (cid:88) − + (cid:88) − (cid:88) − − s + t m s + t m t 1 m m=0 s m=t s m=0 s − − t 1 2 s 2 − t 1 2 sym. (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) = (cid:88) − + (cid:88) − (cid:88)− − s t + m s + t m t 1 m m=0 s m=t s m=0 s − − − − − t 1 s t + m + 1 s s + t m + 1 − t 1 t m 4=.10(cid:88) − (cid:88)+ − (cid:88) − − s t + m s + t m t 1 m m=0 m=t m=0 − − t 1 − s − − t 1 − = (s t + m + 1) + (s + t m + 1) (t m) m=0 m=t − m=0 − t(t 3) − s(s + 1) = (s t + 1)(s + 2t + 1) + 2 2 Now we are left with considering the inequality − − t(t 3) − s(s + 1) (s t + 1)(s + 2t + 1) + > k = s + t 2 2 ⇔ − − s2 3t2 + 2st + s 3t + 2 > 0 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (a)

label: list

text: k

text: s

text: for

text: N

text: (b)

text: k

text: for

text: N

text: (c)

text: k

text: for

text: N

text: Proof:

label: paragraph

text: (a)

text: N

text: If

text: k

text: s

text: then

text: k

text: and

text: thus

text: ≤k

text: s

text: k

text: k

text: s

text: k

text: k

text: s.

text: Now

text: sy=m.

text: −2

text: s

text: k

text: s

text: s

text: s

text: s

text: s

text: ≤1

text: since

text: we

text: have

text: a

text: peak

text: at

text: s,

text: and

text: thus

text: −2

text: s

text: s

text: s

text: k

text: (b)

text: N

text: If

text: k

text: s

text: then

text: k

text: k

text: (s

text: k

text: m

text: s

text: s

text: s

text: k

text: by

text: part

text: (a)

text: and

text: since

text: the

text: ordinary

text: multinomials

text: are

text: s

text: nonnegative.

text: Now

text: let

text: k

text: s

text: t

text: where

text: t

text: s,

text: i.e.

text: s

text: k

text: Thus

text: k

text: k

text: (s

text: s

text: t

text: t

text: s

text: s

text: s

text: s

text: s

text: t

text: s

text: t

text: m

text: t

text: m

text: s

text: s

text: t

text: s

text: t

text: s

text: t

text: m

text: s

text: t

text: m

text: t

text: m

text: s

text: m=t

text: s

text: s

text: t

text: s

text: t

text: sym.

text: s

text: t

text: m

text: s

text: t

text: m

text: t

text: m

text: s

text: m=t

text: s

text: s

text: t

text: s

text: t

text: m

text: s

text: s

text: t

text: m

text: t

text: t

text: m

text: s

text: t

text: m

text: s

text: t

text: m

text: t

text: m

text: m=t

text: t

text: s

text: t

text: (s

text: t

text: m

text: (s

text: t

text: m

text: (t

text: m)

text: m=t

text: t(t

text: s(s

text: (s

text: t

text: Now

text: we

text: are

text: left

text: with

text: considering

text: the

text: inequality

text: t(t

text: s(s

text: (s

text: t

text: k

text: s

text: t

text: s

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ⊕ Deﬁnition 3.2: Let R := K[x , . . . , x ]. Let M = ∈NM be a ﬁnitely 0 n i i generated positively graded R module. Deﬁne the Hilbert function of M as N → N χ : M 0 0 (cid:55)→ (cid:88) i dim (M ) R i and the Hilbert series of M as H := χ (i)T i. M M ∈N ∀ ∈ N i So χ(D) = χ (D) D . R/I ∈ Deﬁnition 3.3: (see also [Fr¨o85]) A form G K[x , . . . , x ] of degree d is 0 n called generic if all monomials of degree d in K[x , . . . , x ] have non-zero 0 n coeﬃcients in G, and those coeﬃcients are algebraically independent over the prime ﬁeld of K. Lemma 3.4: The Hilbert series of an ideal generated by a generic system of forms depends only on the ﬁeld characteristic, the rank n, and the degrees of the forms. If char K = 0, we call it the generic Hilbert series of type (n + 1; m; d , . . . , d ) where m is the number of forms. (For us, m = n + c.) 1 m (cid:3) Proof: See [Die04]. ∈ Proposition 3.5: Let K be a ﬁeld (any characteristic), let F , . . . , F 1 m R := K[x , . . . , x ] be forms of degree d , . . . , d (not necessarily generic). 0 n (cid:67) 1 m Let I := (F , . . . , F ) R. Let H be the generic Hilbert series of type 1 m ≥ g (n + 1; m; d , . . . , d ). Then H H coeﬃcient-wise. 1 m R/I g (cid:3) Proof: See [Die04]. ∈ Proposition 3.6: Let G , . . . , G = G R be a generic system of forms ≤ 1 m (cid:67) with m n + 1, let d = deg(G). Let J := (G , . . . , G − ) R. Then for all ∈ N 1 m 1 D , the multiplication map 0 · → G : (R/J) (R/J) D D+d (cid:55)→ · ¯ ¯ F G F is injective, and we have a short exact sequence −→ −→· −→ −→ G 0 (R/J) (R/J) (R/(J, G)) 0 D D+d D+d ∈ Proposition 3.7: Le(cid:81)t G , . . . , G R be a generic system of forms of de- ≤1 m grees d , . . . , d with m n + 1. Then 1 m − m (1 T dj) H = j=1− . R/(G1,...,Gm) (1 T )n+1 5 ##LTLine##

text: Deﬁnition

text: Let

text: R

text: K[x

text: x

text: Let

text: M

text: ∈NM

text: be

text: a

text: ﬁnitely

text: n

text: i

text: i

text: generated

text: positively

text: graded

text: R

text: module.

text: Deﬁne

text: the

text: Hilbert

text: function

text: of

text: M

text: as

text: N

text: N

text: χ

text: M

text: i

text: dim

text: (M

text: R

text: i

text: and

text: the

text: Hilbert

text: series

text: of

text: M

text: as

text: H

text: χ

text: (i)T

text: i.

text: M

text: M

text: ∈N

text: N

text: i

text: So

text: χ(D)

text: χ

text: (D)

text: D

text: R/I

text: Deﬁnition

text: (see

text: also

text: A

text: form

text: G

text: K[x

text: x

text: of

text: degree

text: d

text: is

text: n

text: called

text: generic

text: if

text: all

text: monomials

text: of

text: degree

text: d

text: in

text: K[x

text: x

text: have

text: non-zero

text: n

text: coeﬃcients

text: in

text: G,

text: and

text: those

text: coeﬃcients

text: are

text: algebraically

text: independent

text: over

text: the

text: prime

text: ﬁeld

text: of

text: K.

text: Lemma

text: The

text: Hilbert

text: series

text: of

text: an

text: ideal

text: generated

text: by

text: a

text: generic

text: system

text: of

text: forms

text: depends

text: only

text: on

text: the

text: ﬁeld

text: characteristic,

text: the

text: rank

text: n,

text: and

text: the

text: degrees

text: of

text: the

text: forms.

text: If

text: char

text: K

text: we

text: call

text: it

text: the

text: generic

text: Hilbert

text: series

text: of

text: type

text: (n

text: m;

text: d

text: d

text: where

text: m

text: is

text: the

text: number

text: of

text: forms.

text: (For

text: us,

text: m

text: n

text: c.)

text: m

text: Proof:

text: See

text: Proposition

text: Let

text: K

text: be

text: a

text: ﬁeld

text: (any

text: characteristic),

text: let

text: F

text: F

text: m

text: R

text: K[x

text: x

text: be

text: forms

text: of

text: degree

text: d

text: d

text: (not

text: necessarily

text: generic).

text: n

text: m

text: Let

text: I

text: (F

text: F

text: R.

text: Let

text: H

text: be

text: the

text: generic

text: Hilbert

text: series

text: of

text: type

text: m

text: g

text: (n

text: m;

text: d

text: d

text: Then

text: H

text: H

text: coeﬃcient-wise.

text: m

text: R/I

text: g

text: Proof:

text: See

text: Proposition

text: Let

text: G

text: G

text: G

text: R

text: be

text: a

text: generic

text: system

text: of

text: forms

text: m

text: with

text: m

text: n

text: let

text: d

text: deg(G).

text: Let

text: J

text: (G

text: G

text: R.

text: Then

text: for

text: all

text: N

text: m

text: D

text: the

text: multiplication

text: map

text: G

text: (R/J)

text: (R/J)

text: D

text: D+d

text: F

text: G

text: F

text: is

text: injective,

text: and

text: we

text: have

text: a

text: short

text: exact

text: sequence

text: G

text: (R/J)

text: (R/J)

text: (R/(J,

text: G))

text: D

text: D+d

text: D+d

text: Proposition

text: G

text: G

text: R

text: be

text: a

text: generic

text: system

text: of

text: forms

text: of

text: de-

text: ≤1

text: m

text: grees

text: d

text: d

text: with

text: m

text: n

text: Then

text: m

text: m

text: T

text: dj)

text: H

text: T

text: ##LTLine##


text: (cid:0) (cid:1) ∈ Corollary 3.9: If f , . . . , f K[x , . . . , x ] (i.e. c = 1) with deg(f ) = d 1≥ n+1 1 n i for all i, then χ(D) n+1 − . Furthermore, if all the forms are generic, D d (cid:0)1 (cid:1) then equality holds. Proof: Take c = 1 in Theorem 3.8, and recall that the coeﬃcient of T D − in (1 + T + . . . + T d 1)n+1 is n+1 − . The second statement follows from D d 1 (cid:3) Proposition 3.7. ≤ In Section we use this Corollary to ﬁnd the smallest D such that χ(D) D (and XL succeeds by Theorem 3.1) in the c = 1 case. Remark 3.10: We remark that there are three possibly diﬀerent D’s under discussion: (cid:0) (cid:1) ∗ 1. the smallest D such that the XL algorithm terminates (call it D ), ≤ 2. the smallest D such that χ(D) D (call it D ), ≤ χ 3. the smallest D such th∗a≤t nD+1 d−1 D (call it Dm). Theorem 3.1 implies that D D . In the case c = 1, Corollary 3.9 implies ≤ χ that D D , and D = D when the equations are generic. m χ m χ In Section we investigate the relationship between these when c = 1. At ∗ the end of the section we will conjecture that D = D = D when c = 1 χ m and the equations are generic, and provide evidence. 4 Ordinary Multinomials This section is independent of the rest of the paper. We will prove here that ordinary multinomials are strongly unimodal, and some inequalities. Deﬁnition 4.1: A sequence s , s , . . . , s of integers is said to be unimodal ≤0 ≤1 N if there is an integer t with 0 t N such that ≤ ≤ · · · ≤ ≥ ≥ · · · ≥ s s s , s s s . 0 1 t t t+1 N (cid:0) (cid:1) A unimodal sequence is said to be strongly unimodal if all the inequalities are strict, except that s = s may hold. For example, the sequence of t t+1 binomial coeﬃcients N (k = 0, 1, . . . , N) is strongly unimodal. k Remark 4.2: We remark that there are diﬀerent deﬁnitions of strongly uni- modal in the literature. One deﬁnition is the same as ours except it does not allow s = s , in which case the binomial coeﬃcients are strongly unimodal t t+1 only for N even. (cid:0) (cid:1) Deﬁnition 4.3: The coeﬃcient of T k in (1+T +. . .+T s)N is called ordinary multinomial or generalized binomial coeﬃcient of order s and is denoted by N . k s 7

text: Corollary

text: If

text: f

text: f

text: K[x

text: x

text: (i.e.

text: c

text: with

text: deg(f

text: d

text: 1≥

text: n

text: i

text: for

text: all

text: i,

text: then

text: χ(D)

text: Furthermore,

text: if

text: all

text: the

text: forms

text: are

text: generic,

text: D

text: d

text: then

text: equality

text: holds.

text: Proof:

text: Take

text: c

text: in

text: Theorem

text: and

text: recall

text: that

text: the

text: coeﬃcient

text: of

text: T

text: D

text: in

text: T

text: T

text: d

text: is

text: The

text: second

text: statement

text: follows

text: from

text: D

text: d

text: Proposition

text: In

text: Section

text: we

text: use

text: this

text: Corollary

text: to

text: ﬁnd

text: the

text: smallest

text: D

text: such

text: that

text: χ(D)

text: D

text: (and

text: XL

text: succeeds

text: by

text: Theorem

text: in

text: the

text: c

text: case.

text: Remark

text: We

text: remark

text: that

text: there

text: are

text: three

text: possibly

text: diﬀerent

text: D’s

text: under

text: discussion:

text: the

text: smallest

text: D

text: such

text: that

text: the

text: XL

text: algorithm

text: terminates

text: (call

text: it

text: D

text: the

text: smallest

text: D

text: such

text: that

text: χ(D)

text: D

text: (call

text: it

text: D

text: χ

text: the

text: smallest

text: D

text: such

text: th∗a≤t

text: D

text: (call

text: it

text: Dm).

text: Theorem

text: implies

text: that

text: D

text: D

text: In

text: the

text: case

text: c

text: Corollary

text: implies

text: χ

text: that

text: D

text: D

text: and

text: D

text: D

text: when

text: the

text: equations

text: are

text: generic.

text: m

text: χ

text: m

text: χ

text: In

text: Section

text: we

text: investigate

text: the

text: relationship

text: between

text: these

text: when

text: c

text: At

text: the

text: end

text: of

text: the

text: section

text: we

text: will

text: conjecture

text: that

text: D

text: D

text: D

text: when

text: c

text: χ

text: m

text: and

text: the

text: equations

text: are

text: generic,

text: and

text: provide

text: evidence.

text: Ordinary

text: Multinomials

text: This

text: section

text: is

text: independent

text: of

text: the

text: rest

text: of

text: the

text: paper.

text: We

text: will

text: prove

text: here

text: that

text: ordinary

text: multinomials

text: are

text: strongly

text: unimodal,

text: and

text: some

text: inequalities.

text: Deﬁnition

text: A

text: sequence

text: s

text: s

text: s

text: of

text: integers

text: is

text: said

text: to

text: be

text: unimodal

text: ≤0

text: ≤1

text: N

text: if

text: there

text: is

text: an

text: integer

text: t

text: with

text: t

text: N

text: such

text: that

text: s

text: s

text: s

text: s

text: s

text: s

text: t

text: t

text: N

text: A

text: unimodal

text: sequence

text: is

text: said

text: to

text: be

text: strongly

text: unimodal

text: if

text: all

text: the

text: inequalities

text: are

text: strict,

text: except

text: that

text: s

text: s

text: may

text: hold.

text: For

text: example,

text: the

text: sequence

text: of

text: t

text: binomial

text: coeﬃcients

text: N

text: (k

text: N)

text: is

text: strongly

text: unimodal.

text: k

text: Remark

text: We

text: remark

text: that

text: there

text: are

text: diﬀerent

text: deﬁnitions

text: of

text: strongly

text: uni-

text: modal

text: in

text: the

text: literature.

text: One

text: deﬁnition

text: is

text: the

text: same

text: as

text: ours

text: except

text: it

text: does

text: not

text: allow

text: s

text: s

text: in

text: which

text: case

text: the

text: binomial

text: coeﬃcients

text: are

text: strongly

text: unimodal

text: t

text: only

text: for

text: N

text: even.

text: Deﬁnition

text: The

text: coeﬃcient

text: of

text: T

text: k

text: in

text: .+T

text: s)N

text: is

text: called

text: ordinary

text: multinomial

text: or

text: generalized

text: binomial

text: coeﬃcient

text: of

text: order

text: s

text: and

text: is

text: denoted

text: by

text: N

text: k

text: s


text: (cid:0) (cid:1) Combinatorially, N is the number of diﬀerent ways of distributing k k s objects among N boxes, where each box contains at most s objects. See [Bol86] and [Bon93] for an introduction. N = 0: 1 N = 1: 1 1 1 1 N = 2: 1 2 3 4 3 2 1 N = 3: 1 3 6 10 12 12 (cid:0) 1(cid:1)0 6 3 1 N = 4: 1 4 10 20 31 40 44 40 31 20 10 4 1 (cid:0) (cid:1) Table 1: Triangle of ordinary multinomials N with s = 3 and k = 0...sN k s Proposition 4.4: (a) N = 0 for k < 0 and k > sN. k s (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) (b) For s = 1, th(cid:88)e ordinary multinomials are the usual binomial coeﬃcients. (cid:98) (cid:99) − − k/(s+1) N − N k i(s + 1) + N 1 (c) (cid:18) (cid:19) = ( 1)i (cid:18) −(cid:19) (cid:88) k i k i(s + 1) s i=0 N N (d) = k j , . . . , j s j1+...+js+1=N 1 s+1 j2+2j3+...+sjs+1=k − Proof: (c) follo(cid:0)ws(cid:1)from(cid:0) expa(cid:1)nding (1 + T + . . . + T s)N = (1 T−s+1)N . (1 T)N (cid:3) (d) follows from the multinomial theorem. Lemma 4.5: N = N− , i.e. th(cid:0)e ordina(cid:1)ry m(cid:0)ultinom(cid:1)ials are symmetric. k s sN k s { Proof: Using P(cid:0)rop(cid:1)ositi(cid:80)on 4.4(cid:0)(d), (cid:1)if j , . . . , j satisfy j1+...+js+1=N , then − 1 s+1 j2+2j3+...+sjs+1=k (cid:3) j + 2j − + . . . + sj = sN k and N = N . s s 1 1 − js+1,...,j1 j1,...,js+1 Lemma 4.6: N = s N− 1 k s m=0 k m s Proof: Use Proposition 4.4 (d) and the recurrence relation of multinomial (cid:3) coeﬃcients. ≥ Theo(cid:18)rem(cid:19)4.7:(cid:18)Th(cid:19)e ordinary m(cid:18)ultino(cid:19)mials(cid:18)are st(cid:19)rongly unim(cid:18)odal(cid:19). For N 2 we have N N · · · N N · · · N < < < (cid:98) (cid:99) = (cid:100) (cid:101) > > 0 1 sN sN sN s s 2 s 2 s s 8 ##LTLine## ##LTLine## ##LTLine##

text: Combinatorially,

text: N

text: is

text: the

text: number

text: of

text: diﬀerent

text: ways

text: of

text: distributing

text: k

text: k

text: s

text: objects

text: among

text: N

text: boxes,

text: where

text: each

text: box

text: contains

text: at

text: most

text: s

text: objects.

text: See

text: and

text: for

text: an

text: introduction.

text: N

label: table

text: N

text: N

text: N

label: caption

text: N

text: Table

text: Triangle

text: of

text: ordinary

text: multinomials

text: N

text: with

text: s

text: and

text: k

text: k

text: s

text: Proposition

text: (a)

text: N

text: for

text: k

text: and

text: k

text: sN.

text: k

text: s

text: (b)

text: For

text: s

text: ordinary

text: multinomials

text: are

text: the

text: usual

text: binomial

text: coeﬃcients.

text: N

text: N

text: k

text: i(s

text: N

text: (c)

text: k

text: i

text: k

text: i(s

text: s

text: N

text: N

text: (d)

text: k

text: j

text: j

text: s

text: Proof:

text: (c)

text: T

text: T

text: s)N

text: T)N

text: (d)

text: follows

text: from

text: the

text: multinomial

text: theorem.

text: Lemma

text: N

text: N−

text: i.e.

text: are

text: symmetric.

text: k

text: s

text: sN

text: k

text: s

text: Proof:

text: Using

text: j

text: j

text: satisfy

text: then

text: j

text: sj

text: sN

text: k

text: and

text: N

text: N

text: s

text: s

text: Lemma

text: N

text: s

text: N−

text: k

text: s

text: k

text: m

text: s

text: Proof:

text: Use

text: Proposition

text: (d)

text: and

text: the

text: recurrence

text: relation

text: of

text: multinomial

text: coeﬃcients.

text: ordinary

text: For

text: N

text: we

text: have

text: N

text: N

text: N

text: N

text: N

text: sN

text: sN

text: sN

text: s

text: s

text: s

text: s

text: s

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Linear response and correlation of a self-propelled particle in the presence of external ﬁelds. 13 (a) (b) Figure 3: Responses functions computed via numerical simulations from the AOUP ( ) model and R (t) A the UCNA-model ( ), for diﬀerent values of : and . The graphs are obtained for R (t) ζ ζ = 10, 0.5 λ = 1 U systems under the action of a harmonic potential U = λX2/2 ( panel (a)) and a potential U = λX4/4 (panel (b)). (a) (b) (c) Figure 4: Response functions and computed via numerical simulations from the AOUP R (t) R (t) A V model and response of the UCNA in the case of small : and . The graphs (a) and R (t) ζ ζ = 0.2 λ = 1 U (b) are obtained for systems under the action of a harmonic potential U = λX2/2 and a quartic one − U = λX4/4, respectively. The graph (c) is obtained for the double well potential U = λ(X4/4 X2/2), for . ζ = 0.5 with respect to , as is shown in Fig.2. On the other hand, in the harmonic case is very close R (t) R (t) V U to , but in the initial stage the UCNA response is non-monotonic and only in a later stage behaves R (t) V (cid:28) very closely to . In fact, is only an approximation of and fails in the limit . This R (t) R (t) R (t) ζ 1 V U V has been directly veriﬁed both for the harmonic potential (Fig. 4a) and the quartic potential (Fig. 4b). In Fig.4 we compare and in the case of a double well potential when is small and so the system R R ζ V A is far from equilibrium. As expected by the previous cases, is slower than . Both responses R (t) R (t) ∼ V A show a ﬁrst exponential relaxation for and a relaxation slower than an exponential for a much t 1 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: Linear

text: response

text: and

text: correlation

text: of

text: a

text: self-propelled

text: particle

text: in

text: the

text: presence

text: of

text: external

text: ﬁelds.

text: (a)

text: (b)

text: Figure

text: Responses

text: functions

text: computed

text: via

text: numerical

text: simulations

text: from

text: the

text: AOUP

text: model

text: and

text: R

text: (t)

text: A

text: the

text: UCNA-model

text: for

text: diﬀerent

text: values

text: of

text: and

text: The

text: graphs

text: are

text: obtained

text: for

text: R

text: (t)

text: ζ

text: ζ

text: λ

text: U

text: systems

text: under

text: the

text: action

text: of

text: a

text: harmonic

text: potential

text: U

text: panel

text: (a))

text: and

text: a

text: potential

text: U

text: (panel

text: (b)).

text: (a)

text: (b)

text: (c)

text: Figure

text: Response

text: functions

text: and

text: computed

text: via

text: numerical

text: simulations

text: from

text: the

text: AOUP

text: R

text: (t)

text: R

text: (t)

text: A

text: V

text: model

text: and

text: response

text: of

text: the

text: UCNA

text: in

text: the

text: case

text: of

text: small

text: and

text: The

text: graphs

text: (a)

text: and

text: R

text: (t)

text: ζ

text: ζ

text: λ

text: U

text: (b)

text: are

text: obtained

text: for

text: systems

text: under

text: the

text: action

text: of

text: a

text: harmonic

text: potential

text: U

text: and

text: a

text: quartic

text: one

text: U

text: respectively.

text: The

text: graph

text: (c)

text: is

text: obtained

text: for

text: the

text: double

text: well

text: potential

text: U

text: for

text: ζ

text: with

text: respect

text: to

text: as

text: is

text: shown

text: in

text: On

text: the

text: other

text: hand,

text: in

text: the

text: harmonic

text: case

text: is

text: very

text: close

text: R

text: (t)

text: R

text: (t)

text: V

text: U

text: to

text: but

text: in

text: the

text: initial

text: stage

text: the

text: UCNA

text: response

text: is

text: non-monotonic

text: and

text: only

text: in

text: a

text: later

text: stage

text: behaves

text: R

text: (t)

text: V

text: very

text: closely

text: to

text: In

text: fact,

text: is

text: only

text: an

text: approximation

text: of

text: and

text: fails

text: in

text: the

text: limit

text: This

text: R

text: (t)

text: R

text: (t)

text: R

text: (t)

text: ζ

text: V

text: U

text: V

text: has

text: been

text: directly

text: veriﬁed

text: both

text: for

text: the

text: harmonic

text: potential

text: (Fig.

text: and

text: the

text: quartic

text: potential

text: (Fig.

text: In

text: we

text: compare

text: and

text: in

text: the

text: case

text: of

text: a

text: double

text: well

text: potential

text: when

text: is

text: small

text: and

text: so

text: the

text: system

text: R

text: R

text: ζ

text: V

text: A

text: is

text: far

text: from

text: equilibrium.

text: As

text: expected

text: by

text: the

text: previous

text: cases,

text: is

text: slower

text: than

text: Both

text: responses

text: R

text: (t)

text: R

text: (t)

text: V

text: A

text: show

text: a

text: ﬁrst

text: exponential

text: relaxation

text: for

text: and

text: a

text: relaxation

text: slower

text: than

text: an

text: exponential

text: for

text: a

text: much

text: t

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: Linear response and correlation of a self-propelled particle in the presence of external ﬁelds. 9 3. Results In the following, we shall present some results illustrating the predictions of the theory in some simple cases. We have performed the simulations for three diﬀerent potentials : (a) harmonic potential U(X) − U(X) = λX2/2, (b) quartic potential U(X) = λX4/4, (c) double well potential U(X) = λ(X4/2 X2/2). The numerical computations of , both from data and FDR Eq.(25), were performed using the R(t) Euler-Maruyama method [27], neglecting order (∆t)5/2. (cid:28) 3.1. Response in the limit ζ 1 In the case (a) the probability distribution of the system can be computed exactly and therefore ∼ − we have an exact expression for the response: R (t) e tλ/ζ. In the cases (b) and (c) we know the (cid:28)A probability distribution as a series in powers of so that we can obtain the FDR only perturbatively. 1/ζ 1 (cid:29) Therefore, the numerical approach is necessary when the limit doesn’t hold. In Fig. 1 we show ζ 1 for the three diﬀerent potentials and diﬀerent values of . Let us ﬁrst discuss the case (a) and (b): R (t) ζ A when is large, we are near the delta correlated noise, closed to the equilibrium situation. Therefore the ζ (a) (b) (c) Figure 1: Responses for the AOUP model computed, via numerical simulation, for diﬀerent values R (t) A of ζ by setting λ = 1. In ﬁgure (a) are plotted the responses for the harmonic potential λX2/2. The − plots (b) and (c) correspond to a quartic potential λX4/4 and a double well potential λ(X4/4 X2/2), respectively. shape of the potential does not change the form of the response, which decays roughly as an exponential. ∼ (cid:28) When or the results relative to the two potentials display large diﬀerences increasing as ζ 1 ζ 1 decreases. In particular, when the attractive force becomes stronger, the response becomes slower, ζ as we can see in Fig. 1. This is a consequence of the departure of the system from thermodynamic equilibrium: indeed the detailed balance holds only in the harmonic case [29] when the drag coeﬃcient in the variables is constant. Otherwise, is not constant, and decreasing the system goes far (X, V ) g(X) ζ from equilibrium. Indeed, where is small, in the harmonic case the shape obtained is the one predicted ζ ∼ − by the theoretical computations e λt/ζ. In the other cases we can distinguish between two regimes: ∼ ∼ (cid:29) up to (in dimensional units this corresponds to ) there is fast relaxation, while for t 1 t l/v t 1 T (cid:29) there is a relaxation with an eﬀective characteristic time . The presence of these two regimes t ζ slow is a non-equilibrium eﬀect and is more evident when the activity is large ( small). The presence of ζ two times scales, when the system is far from equilibrium, is a clear consequence of the accumulation of ##LTFigure## ##LTFigure## ##LTFigure##

text: Linear

text: response

text: and

text: correlation

text: of

text: a

text: self-propelled

text: particle

text: in

text: the

text: presence

text: of

text: external

text: ﬁelds.

label: section

text: Results

text: In

text: the

text: following,

text: we

text: shall

text: present

text: some

text: results

text: illustrating

text: the

text: predictions

text: of

text: the

text: theory

text: in

text: some

text: simple

text: cases.

text: We

text: have

text: performed

text: the

text: simulations

text: for

text: three

text: diﬀerent

text: potentials

text: (a)

text: harmonic

text: potential

text: U(X)

text: U(X)

text: (b)

text: quartic

text: potential

text: U(X)

text: (c)

text: double

text: well

text: potential

text: U(X)

text: The

text: numerical

text: computations

text: of

text: both

text: from

text: data

text: and

text: FDR

text: were

text: performed

text: using

text: the

text: R(t)

text: Euler-Maruyama

text: method

text: neglecting

text: order

text: Response

text: in

text: the

text: limit

text: ζ

text: In

text: the

text: case

text: (a)

text: the

text: probability

text: distribution

text: of

text: the

text: system

text: can

text: be

text: computed

text: exactly

text: and

text: therefore

text: we

text: have

text: an

text: exact

text: expression

text: for

text: the

text: response:

text: R

text: (t)

text: e

text: tλ/ζ.

text: In

text: the

text: cases

text: (b)

text: and

text: (c)

text: we

text: know

text: the

text: probability

text: distribution

text: as

text: a

text: series

text: in

text: powers

text: of

text: so

text: that

text: we

text: can

text: obtain

text: the

text: FDR

text: only

text: perturbatively.

text: Therefore,

text: the

text: numerical

text: approach

text: is

text: necessary

text: when

text: the

text: limit

text: doesn’t

text: hold.

text: In

text: Fig.

text: we

text: show

text: ζ

text: for

text: the

text: three

text: diﬀerent

text: potentials

text: and

text: diﬀerent

text: values

text: of

text: Let

text: us

text: ﬁrst

text: discuss

text: the

text: case

text: (a)

text: and

text: (b):

text: R

text: (t)

text: ζ

text: A

text: when

text: is

text: large,

text: we

text: are

text: near

text: the

text: delta

text: correlated

text: noise,

text: closed

text: to

text: the

text: equilibrium

text: situation.

text: Therefore

text: the

text: ζ

text: (a)

text: (b)

text: (c)

text: Figure

text: Responses

text: for

text: the

text: AOUP

text: model

text: computed,

text: via

text: numerical

text: simulation,

text: for

text: diﬀerent

text: values

text: R

text: (t)

text: A

text: of

text: ζ

text: by

text: setting

text: λ

text: In

text: ﬁgure

text: (a)

text: are

text: plotted

text: the

text: responses

text: for

text: the

text: harmonic

text: potential

text: The

text: plots

text: (b)

text: and

text: (c)

text: correspond

text: to

text: a

text: quartic

text: potential

text: and

text: a

text: double

text: well

text: potential

text: respectively.

text: shape

text: of

text: the

text: potential

text: does

text: not

text: change

text: the

text: form

text: of

text: the

text: response,

text: which

text: decays

text: roughly

text: as

text: an

text: exponential.

text: When

text: or

text: the

text: results

text: relative

text: to

text: the

text: two

text: potentials

text: display

text: large

text: diﬀerences

text: increasing

text: as

text: ζ

text: ζ

text: decreases.

text: In

text: particular,

text: when

text: the

text: attractive

text: force

text: becomes

text: stronger,

text: the

text: response

text: becomes

text: slower,

text: ζ

text: as

text: we

text: can

text: see

text: in

text: Fig.

text: This

text: is

text: a

text: consequence

text: of

text: the

text: departure

text: of

text: the

text: system

text: from

text: thermodynamic

text: equilibrium:

text: indeed

text: the

text: detailed

text: balance

text: holds

text: only

text: in

text: the

text: harmonic

text: case

text: when

text: the

text: drag

text: coeﬃcient

text: in

text: the

text: variables

text: is

text: constant.

text: Otherwise,

text: is

text: not

text: constant,

text: and

text: decreasing

text: the

text: system

text: goes

text: far

text: (X,

text: V

text: g(X)

text: ζ

text: from

text: equilibrium.

text: Indeed,

text: where

text: is

text: small,

text: in

text: the

text: harmonic

text: case

text: the

text: shape

text: obtained

text: is

text: the

text: one

text: predicted

text: ζ

text: by

text: the

text: theoretical

text: computations

text: e

text: λt/ζ.

text: In

text: the

text: other

text: cases

text: we

text: can

text: distinguish

text: between

text: two

text: regimes:

text: up

text: to

text: (in

text: dimensional

text: units

text: this

text: corresponds

text: to

text: there

text: is

text: fast

text: relaxation,

text: while

text: for

text: t

text: t

text: l/v

text: t

text: T

text: there

text: is

text: a

text: relaxation

text: with

text: an

text: eﬀective

text: characteristic

text: time

text: The

text: presence

text: of

text: these

text: two

text: regimes

text: t

text: ζ

text: slow

text: is

text: a

text: non-equilibrium

text: eﬀect

text: and

text: is

text: more

text: evident

text: when

text: the

text: activity

text: is

text: large

text: small).

text: The

text: presence

text: of

text: ζ

text: two

text: times

text: scales,

text: when

text: the

text: system

text: is

text: far

text: from

text: equilibrium,

text: is

text: a

text: clear

text: consequence

text: of

text: the

text: accumulation

text: of

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: M focus on the case where is highly singular and only comment on the more Nt straightforward case. 4.1. First preconditioner The ﬁrst preconditioner we introduce is based on the block diagonal structure PD, but with the(cid:34) (1, 1) block and Sc(cid:35)hur(cid:34)complement rep(cid:35)laced with suitable approximations. For the (1, 1) block, we write(cid:99)that (cid:98) − M M A = γ 1 Nt 0M ≈ Nt 0M =: A, (cid:99) 0 β τ 0 β τ M − M where approximates the highly singular matrix γ 1 . As suggested Nt Nt by Benzi, Haber and Taralli in [6], all zero diagonal entries in the (1, 1) block are replaced with µ within the preconditioner, where this parameter reﬂects the mean ratio of diagonal entries between the ﬁrst and second terms of the Schur complement. Since the (1, 1) block is highly singular we deﬁne the Schur complement of the “perturbed” system a(cid:99)s QA M− A Q 1 QJ M− J Q S = (m) 1 (m)T + (y) 1 (y)T . Nt β τ The approach we use to approximate this matrix follows the matching strategy (cid:0) (cid:1) (cid:0) (cid:1) introduced in [32,(cid:98)19, 33, 20], where we(cid:99)approximate S by QA M M− A Q M S = (m) + 1 (m)T + , (15) 1 1 (cid:99) Nt 2 M M− M with the desire that the term 1 accurately captures the second 1 Nt 2 term of the exact Schur(cid:99)complement, that is: M M− M ≈ 1 QJ M− J Q 1 (y) 1 (y)T . 1 Nt 2 β τ (cid:0) M M (cid:1) A possible selection of the matrices , is as follows: (cid:99) 1 2 M = MT = √1 QJ (y)M−1J (y)T Q 1/2M1/2, (16) 1 2 β τ Nt A further saving in the required computational cost may be achieved by (cid:104) (cid:0) (cid:1)(cid:105) (cid:2) (cid:0) (cid:1)(cid:3) replacing these matrices by the (cid:99)diagonal approximations: M = M = √1 diag M 1/2 diag QJ (y)M−1J (y)T Q 1/2 , 1 2 β τ Nt (cid:99) which leads to a preconditioner that may be applied cheaply in practice. We M M− note that, whereas the matrices 1/2 and 1 appear complicated to apply, Nt M M they are in fact straightforward as each of the matrices and contain Nt 13 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: M

text: focus

text: on

text: the

text: case

text: where

text: is

text: highly

text: singular

text: and

text: only

text: comment

text: on

text: the

text: more

text: Nt

text: straightforward

text: case.

text: First

text: preconditioner

text: The

text: ﬁrst

text: preconditioner

text: we

text: introduce

text: is

text: based

text: on

text: the

text: block

text: diagonal

text: structure

text: PD,

text: but

text: with

text: block

text: and

text: with

text: suitable

text: approximations.

text: For

text: the

text: block,

text: we

text: M

text: M

text: A

text: γ

text: Nt

text: Nt

text: A,

text: β

text: τ

text: β

text: τ

text: M

text: M

text: where

text: approximates

text: the

text: highly

text: singular

text: matrix

text: γ

text: As

text: suggested

text: Nt

text: Nt

text: by

text: Benzi,

text: Haber

text: and

text: Taralli

text: in

text: all

text: zero

text: diagonal

text: entries

text: in

text: the

text: block

text: are

text: replaced

text: with

text: µ

text: within

text: the

text: preconditioner,

text: where

text: this

text: parameter

text: reﬂects

text: the

text: mean

text: ratio

text: of

text: diagonal

text: entries

text: between

text: the

text: ﬁrst

text: and

text: second

text: terms

text: of

text: the

text: Schur

text: complement.

text: Since

text: the

text: block

text: is

text: highly

text: singular

text: we

text: deﬁne

text: the

text: Schur

text: complement

text: of

text: the

text: “perturbed”

text: system

text: QA

text: M−

text: A

text: Q

text: QJ

text: M−

text: J

text: Q

text: S

text: (m)

text: (m)T

text: (y)

text: (y)T

text: Nt

text: β

text: τ

text: The

text: approach

text: we

text: use

text: to

text: approximate

text: this

text: matrix

text: follows

text: the

text: matching

text: strategy

text: introduced

text: in

text: where

text: S

text: by

text: QA

text: M

text: M−

text: A

text: Q

text: M

text: S

text: (m)

text: (m)T

text: Nt

text: M

text: M−

text: M

text: with

text: the

text: desire

text: that

text: the

text: term

text: accurately

text: captures

text: the

text: second

text: Nt

text: term

text: of

text: the

text: exact

text: that

text: is:

text: M

text: M−

text: M

text: QJ

text: M−

text: J

text: Q

text: (y)

text: (y)T

text: Nt

text: β

text: τ

text: M

text: M

text: A

text: possible

text: selection

text: of

text: the

text: matrices

text: is

text: as

text: follows:

text: M

text: MT

text: √1

text: QJ

text: (y)T

text: Q

text: β

text: τ

text: Nt

text: A

text: further

text: saving

text: in

text: the

text: required

text: computational

text: cost

text: may

text: be

text: achieved

text: by

text: replacing

text: these

text: matrices

text: by

text: the

text: approximations:

text: M

text: M

text: √1

text: diag

text: M

text: diag

text: QJ

text: (y)T

text: Q

text: β

text: τ

text: Nt

text: which

text: leads

text: to

text: a

text: preconditioner

text: that

text: may

text: be

text: applied

text: cheaply

text: in

text: practice.

text: We

text: M

text: M−

text: note

text: that,

text: whereas

text: the

text: matrices

text: and

text: appear

text: complicated

text: to

text: apply,

text: Nt

text: M

text: M

text: they

text: are

text: in

text: fact

text: straightforward

text: as

text: each

text: of

text: the

text: matrices

text: and

text: contain

text: Nt

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:99) M multiples of identity operators on each diagonal block, and therefore 1/2 and M− Nt 1 solely consist of scaled identity matrices corresponding to each time-step. Whereas the eﬀectiveness of this Schur complement approximation will in- evitably depend to some extent on the numerical behaviour of the solution at each Newton step, the following observation may be readily made (based on the methodology of [20]), guaranteeing(cid:98)the robustness of the sma(cid:98)llest eigenvalue of the preconditioned Schur complement in an ideal setting: − ≥ Lemma 1. The eigenvalues λ of S 1S satisfy λ 1, where S is as deﬁned by M M 1 2 1 (15), and , are given in (16). (cid:98) 1 2 (cid:99) Proof. Due to the symmetry and positive deﬁniteness of S and S , which may M 1 be observed due to (cid:16) Nt being symmetric positive deﬁnite by construction,(cid:17)the eigenvalues may be bounded b(cid:99)y the Rayleigh quotient (cid:0) (cid:1) (cid:0) (cid:1) (cid:98) QA M− A Q (cid:99)− − QJ M− J Q R := vT Sv = vT (m)QAN1t (m)MT +Mβ−1τA1 (Qy) M1 (y)T v. vT S v vT (m) + 1 (m)T + v 1 1 Nt 2 We now observe that we may write (cid:99) aT a + bT b M− A Q √1 M− J Q R = , where a = 1/2 (m)T v, b = 1/2 (y)T v. (a + b)T (a + b) Nt β τ Simple manipulation therefore tells us that 1 − − ≥ ⇔ ≥ 1 ⇔ ≥ 1 (a b)T (a b) 0 aT a + bT b (a + b)T (a + b) R , 2 2 2 which leads to the result. (cid:98) − We highlight that, although the lower bound for the eigenvalues of S 1S 1 can be analysed in detail, the magnitude of the largest eigenvalue will depend on the precise behaviour of the Newton iterates, which we cannot control in general. To provide an illustration of the overall eigenvalue distribution, we present in Fig. 2 the eigenvalues for a particular test problem, for a range of problem sizes and values of β. As is demonstrated by the plots, the eigenvalues are found to become more clustered for ﬁner grids, with the magnitude of the largest eigenvalues fairly robust to changes in regularisation parameter. Applying our approximations of the (1, 1) block and Schur complement leads (cid:99) to a preconditioner of the form    M    0 0 Nt M (cid:98) P = 0 β τ 0 , (17) 1 0 0 S 1 which we can then apply within a Krylov subspace method. 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: M

text: multiples

text: of

text: identity

text: operators

text: on

text: each

text: diagonal

text: block,

text: and

text: therefore

text: and

text: M−

text: Nt

text: solely

text: consist

text: of

text: scaled

text: identity

text: matrices

text: corresponding

text: to

text: each

text: time-step.

text: Whereas

text: the

text: eﬀectiveness

text: of

text: this

text: Schur

text: complement

text: approximation

text: will

text: in-

text: evitably

text: depend

text: to

text: some

text: extent

text: on

text: the

text: numerical

text: behaviour

text: of

text: the

text: solution

text: at

text: each

text: Newton

text: step,

text: the

text: following

text: observation

text: may

text: be

text: readily

text: made

text: (based

text: on

text: the

text: methodology

text: of

text: robustness

text: of

text: the

text: eigenvalue

text: of

text: the

text: preconditioned

text: Schur

text: complement

text: in

text: an

text: ideal

text: setting:

text: Lemma

text: The

text: eigenvalues

text: λ

text: of

text: S

text: satisfy

text: λ

text: where

text: S

text: is

text: as

text: deﬁned

text: by

text: M

text: M

text: and

text: are

text: given

text: in

text: Proof.

text: Due

text: to

text: the

text: symmetry

text: and

text: positive

text: deﬁniteness

text: of

text: S

text: and

text: S

text: which

text: may

text: M

text: be

text: observed

text: due

text: to

text: Nt

text: being

text: symmetric

text: positive

text: deﬁnite

text: by

text: eigenvalues

text: may

text: be

text: bounded

text: the

text: Rayleigh

text: quotient

text: QA

text: M−

text: A

text: Q

text: QJ

text: M−

text: J

text: Q

text: R

text: vT

text: Sv

text: vT

text: (m)MT

text: (Qy)

text: (y)T

text: v.

text: vT

text: S

text: v

text: vT

text: (m)

text: (m)T

text: v

text: Nt

text: We

text: now

text: observe

text: that

text: we

text: may

text: write

text: aT

text: a

text: bT

text: b

text: M−

text: A

text: Q

text: √1

text: M−

text: J

text: Q

text: R

text: where

text: a

text: (m)T

text: v,

text: b

text: (y)T

text: v.

text: (a

text: b)T

text: (a

text: b)

text: Nt

text: β

text: τ

text: Simple

text: manipulation

text: therefore

text: tells

text: us

text: that

text: (a

text: b)T

text: (a

text: b)

text: aT

text: a

text: bT

text: b

text: (a

text: b)T

text: (a

text: b)

text: R

text: which

text: leads

text: to

text: the

text: result.

text: We

text: highlight

text: that,

text: although

text: the

text: lower

text: bound

text: for

text: the

text: eigenvalues

text: of

text: S

text: can

text: be

text: analysed

text: in

text: detail,

text: the

text: magnitude

text: of

text: the

text: largest

text: eigenvalue

text: will

text: depend

text: on

text: the

text: precise

text: behaviour

text: of

text: the

text: Newton

text: iterates,

text: which

text: we

text: cannot

text: control

text: in

text: general.

text: To

text: provide

text: an

text: illustration

text: of

text: the

text: overall

text: eigenvalue

text: distribution,

text: we

text: present

text: in

text: Fig.

text: the

text: eigenvalues

text: for

text: a

text: particular

text: test

text: problem,

text: for

text: a

text: range

text: of

text: problem

text: sizes

text: and

text: values

text: of

text: β.

text: As

text: is

text: demonstrated

text: by

text: the

text: plots,

text: the

text: eigenvalues

text: are

text: found

text: to

text: become

text: more

text: clustered

text: for

text: ﬁner

text: grids,

text: with

text: the

text: magnitude

text: of

text: the

text: largest

text: eigenvalues

text: fairly

text: robust

text: to

text: changes

text: in

text: regularisation

text: parameter.

text: Applying

text: our

text: approximations

text: of

text: the

text: block

text: and

text: Schur

text: complement

text: leads

text: to

text: a

text: preconditioner

text: of

text: the

text: form

text: M

text: Nt

text: M

text: P

text: β

text: τ

text: S

text: which

text: we

text: can

text: then

text: apply

text: within

text: a

text: Krylov

text: subspace

text: method.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text:          − M A Q   QA QJ  γ 1 0 (m)T (m) (y) 0 Nt M J Q M J Q Π 0 β τ (y)T = 0 β τ (y)T , QA QJ − M A Q (m) (y) 0 γ 1 0 (m)T Nt (18)   where the permutation matrix is given by     0 0 I Π := 0 I 0 . I 0 0 (cid:34) (cid:35) (cid:104) (cid:105) (cid:104) (cid:105) The matrix (18) is now of saddle point structure (14), with QA QJ (m) (y) QJ − M A = 0 β τM , B = 0 (y) , C = γ 1 Nt 0 , A Q and a non-zero (2, 2) blockgiven by (m)T .  We may then consider the right preconditioner (cid:101)  QA QJ  (m) (y) 0 M (cid:98) P = 0 β τ 0 , − M − γ 1 0 S Nt 2   with its inverse given by (cid:101)  A − Q− − − − A − J M−  (m) 1 1 β 1τ 1 (m) 1 (y) 1 0 − (cid:98) (cid:98) − − M− (cid:98) P 1 = 0 β 1τ 1 1 0 . − − M A − Q− − − − − − M A − J M− − − γ (cid:98)1S 1 (m) 1 1 γ 1β 1τ 1S 1 (m) 1 (y) 1 S 1 2 Nt 2 Nt 2 The matrix S is designed to approximate the Schur complement of the permuted 2 matrix sys(cid:98)tem, that is ≈ A Q 1 M A − J M− J Q S S = (m)T + (m) 1 (y) 1 (y)T . 2 β τγ Nt (cid:101) Let us now reapply the permutation to the preconditioned system (that is to say − − we propose a preconditioner P such that P 1 = P 1Π), and therefore obtain  2 2    − − − A − J M− A − Q−  0 β 1τ 1 (m) 1 (y) 1 (m) 1 1 − (cid:98) (cid:98) − − M− (cid:98) P 1 = 0 β 1τ 1 1 0 . 2 − − − − − − − M A − J M− − − M A − Q− S 1 γ 1β 1τ 1S 1 (m) 1 (y) 1 γ 1S 1 (m) 1 1 2 Nt 2 Nt (19) 16 ##LTLine##

label: equation

text: M

text: A

text: Q

text: QA

text: QJ

text: γ

text: (m)T

text: (m)

text: (y)

text: Nt

text: M

text: J

text: Q

text: M

text: J

text: Q

text: Π

text: β

text: τ

text: (y)T

text: β

text: τ

text: (y)T

text: QA

text: QJ

text: M

text: A

text: Q

text: (m)

text: (y)

text: γ

text: (m)T

text: Nt

text: where

text: the

text: permutation

text: matrix

text: is

text: given

text: by

text: I

text: Π

text: I

text: I

text: The

text: matrix

text: is

text: now

text: of

text: saddle

text: point

text: structure

text: with

text: QA

text: QJ

text: (m)

text: (y)

text: QJ

text: M

text: A

text: β

text: τM

text: B

text: (y)

text: C

text: γ

text: Nt

text: A

text: Q

text: and

text: a

text: non-zero

text: blockgiven

text: by

text: (m)T

text: We

text: may

text: then

text: consider

text: the

text: right

text: preconditioner

text: QA

text: QJ

text: (m)

text: (y)

text: M

text: P

text: β

text: τ

text: M

text: γ

text: S

text: Nt

text: with

text: its

text: inverse

text: given

text: by

text: A

text: Q−

text: A

text: J

text: M−

text: (m)

text: β

text: 1τ

text: (m)

text: (y)

text: M−

text: P

text: β

text: 1τ

text: M

text: A

text: Q−

text: M

text: A

text: J

text: M−

text: γ

text: (m)

text: γ

text: 1β

text: 1τ

text: (m)

text: (y)

text: S

text: Nt

text: Nt

text: The

text: matrix

text: S

text: is

text: designed

text: to

text: approximate

text: the

text: Schur

text: complement

text: of

text: the

text: permuted

text: matrix

text: that

text: is

text: A

text: Q

text: M

text: A

text: J

text: M−

text: J

text: Q

text: S

text: S

text: (m)T

text: (m)

text: (y)

text: (y)T

text: β

text: τγ

text: Nt

text: Let

text: us

text: now

text: reapply

text: the

text: permutation

text: to

text: the

text: preconditioned

text: system

text: (that

text: is

text: to

text: say

text: we

text: propose

text: a

text: preconditioner

text: P

text: such

text: that

text: P

text: P

text: and

text: therefore

text: obtain

text: A

text: J

text: M−

text: A

text: Q−

text: β

text: 1τ

text: (m)

text: (y)

text: (m)

text: M−

text: P

text: β

text: 1τ

text: M

text: A

text: J

text: M−

text: M

text: A

text: Q−

text: S

text: γ

text: 1β

text: 1τ

text: (m)

text: (y)

text: γ

text: (m)

text: Nt

text: Nt

text: ##LTLine##


text: (cid:0) (cid:1) re-examine the Newton system obtained: (cid:0) (cid:1) ∇ · ∇ · − ∇ · (s ) + (m(cid:126) s ) + ((cid:126)s y) = (cid:0)y + (m(cid:126) y) (cid:1), y t ∗ −y ∇ − m∇ − t ∗ − ∇ β Q Q(cid:126)s y s s p = β Q Qm(cid:126) y p , m p y − − · ∇ − · ∇ − − − · ∇ (s ) (cid:126)s p m(cid:126) s = p m(cid:126) p . p t m p t We wish to apply a meshfree method involving radial basis functions. The approach we use is straight collocation, where the solution sought is a linear sum of RBFs multiplied by unknown coeﬃcients, obtained by solving a matrix system. In more detail, at the k-th time-step we seek a solution for s , s , y m1 s , s by substitu(cid:12)ting (cid:88) (cid:12) (cid:88) m2 p (cid:12) (cid:12) (sy)(cid:12)(cid:12)t=tk = (cid:88)Yj,kφj, (sm1)(cid:12)(cid:12)t=tk = (cid:88) Mj(,1k)φj, j j (s ) = M(2)φ , (s ) = P φ , (20) m2 t=tk j,k j p t=tk j,k j j j (cid:13) (cid:13) into the Newton(cid:13)system(cid:13). The coeﬃcients Y , M(1), M(2), P are un- j,k j,k j,k j,k knowns, and φ denote the radial basis functions used. Each RBF is of the form j − φ = φ(r) where r = (cid:126)x ξ(cid:126) , with (cid:126)x the position vector and ξ(cid:126) the centre of the − RBF. For our initial experiments, we use Gaussian functions φ(r) = e cr2 for a (positive) constant c as our RBFs, though there are many other possibilities of functions with values at speciﬁed points solely depending on their distance from the centre [35, 23]. Consider, for simplicity, the use of backward Euler for time derivatives. Then, at each time-step and RBF centre in space, the collocation proce(cid:88)dure applied(cid:88)to the Newton syste(cid:88)m takes the followi(cid:88)ng form:   1 Yj,kφ(cid:18)j − Yj,k−1φ(cid:19)j (cid:88)+ m1 · Yj,k ∂φj(cid:88)+ m2 · Yj,k ∂φj(cid:88) τ ∂x ∂x 1 2 j j j j + ∂m1 + ∂m2 · Y φ + ∂y · M(1)φ + ∂y · M(2)φ ∂(cid:88)x ∂x (cid:88)j,k j ∂x (cid:0) j,k j ∂x (cid:1) j,k j  1 2 j 1 j 2 j  +(cid:80)y M(1) ∂φj + M(2) ∂φj = − y + ∇ · (m(cid:126) y) , j,k ∂x1 (cid:88) j,k ∂x2 (cid:88) t (cid:0) (cid:1)  (cid:80) j  j ∗ · j Mj(,1k)φj − ·  ∇ − ∇ · − ∗ − ∇ βQ Q y P φ p Y φ = β Q Qm(cid:126) y p , (cid:88) M(2)φ (cid:88) j,k j(cid:88) j,k j (cid:88)  j j,k j j j − 1 − − ∂p · − ∂p · τ Pj,k+1φ(cid:88)j Pj,kφj (cid:88)∂x Mj(,1k)φj(cid:0) ∂x Mj((cid:1),2k)φj 1 2 j j j j − · ∂φ − · ∂φ − − − · ∇ j j m P m P = p m(cid:126) p . 1 j,k 2 j,k t ∂x ∂x 1 2 j j 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: re-examine

text: the

text: Newton

text: system

text: obtained:

text: (s

text: s

text: y)

text: y)

text: y

text: t

text: −y

text: m∇

text: t

text: β

text: Q

text: y

text: s

text: s

text: p

text: β

text: Q

text: y

text: p

text: m

text: p

text: y

text: (s

text: p

text: s

text: p

text: p

text: p

text: t

text: m

text: p

text: t

text: We

text: wish

text: to

text: apply

text: a

text: meshfree

text: method

text: involving

text: radial

text: basis

text: functions.

text: The

text: approach

text: we

text: use

text: is

text: straight

text: collocation,

text: where

text: the

text: solution

text: sought

text: is

text: a

text: linear

text: sum

text: of

text: RBFs

text: multiplied

text: by

text: unknown

text: coeﬃcients,

text: obtained

text: by

text: solving

text: a

text: matrix

text: system.

text: In

text: more

text: detail,

text: at

text: the

text: k-th

text: time-step

text: we

text: seek

text: a

text: solution

text: for

text: s

text: s

text: y

text: s

text: s

text: by

text: p

text: j

text: j

text: (s

text: (s

text: P

text: φ

text: t=tk

text: j,k

text: j

text: p

text: t=tk

text: j,k

text: j

text: j

text: j

text: into

text: the

text: The

text: coeﬃcients

text: Y

text: P

text: are

text: un-

text: j,k

text: j,k

text: j,k

text: j,k

text: knowns,

text: and

text: φ

text: denote

text: the

text: radial

text: basis

text: functions

text: used.

text: Each

text: RBF

text: is

text: of

text: the

text: form

text: j

text: φ

text: φ(r)

text: where

text: r

text: with

text: the

text: position

text: vector

text: and

text: the

text: centre

text: of

text: the

text: RBF.

text: For

text: our

text: initial

text: experiments,

text: we

text: use

text: Gaussian

text: functions

text: φ(r)

text: e

text: for

text: a

text: (positive)

text: constant

text: c

text: as

text: our

text: RBFs,

text: though

text: there

text: are

text: many

text: other

text: possibilities

text: of

text: functions

text: with

text: values

text: at

text: speciﬁed

text: points

text: solely

text: depending

text: on

text: their

text: distance

text: from

text: the

text: centre

text: Consider,

text: for

text: simplicity,

text: the

text: use

text: of

text: backward

text: Euler

text: for

text: time

text: derivatives.

text: Then,

text: at

text: each

text: time-step

text: and

text: RBF

text: centre

text: in

text: space,

text: the

text: collocation

text: the

text: Newton

text: takes

text: the

text: form:

text: Yj,k

text: Yj,k

text: τ

text: ∂x

text: ∂x

text: j

text: j

text: j

text: j

text: ∂m1

text: Y

text: φ

text: ∂y

text: ∂y

text: ∂x

text: j

text: ∂x

text: j,k

text: j

text: ∂x

text: j,k

text: j

text: j

text: 1

text: j

text: j

text: ∂φj

text: ∂φj

text: y

text: y)

text: j,k

text: j,k

text: t

text: j

text: j

text: j

text: βQ

text: Q

text: y

text: P

text: φ

text: p

text: Y

text: φ

text: β

text: Q

text: y

text: p

text: j,k

text: j,k

text: j

text: j

text: j,k

text: j

text: j

text: j

text: ∂p

text: ∂p

text: τ

text: Pj,kφj

text: ∂x

text: j

text: j

text: j

text: j

text: ∂φ

text: ∂φ

text: j

text: j

text: m

text: P

text: m

text: P

text: p

text: p

text: j,k

text: j,k

text: t

text: ∂x

text: ∂x

text: j

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2. The optimal transport problem The problem(cid:90)we examine in this paper is(cid:90)one(cid:90) of minimising the functional E 1 (cid:90) (cid:90)− δ 1 − (y, m(cid:126) ) = (y((cid:126)x, 1) y ((cid:126)x))2 dΩ + (y((cid:126)x, t) y¯((cid:126)x, t))2 dΩ dt 1 2γ 2 Ω 0 Ω (1) β 1 + (Qm(cid:126) ((cid:126)x, t))2 dΩ dt, 2 0 Ω where β and γ are (positive) parameters that can be understood as regulari- sation or penalty parameters. The parameter γ is chosen in such a way that the computed state y((cid:126)x, 1) is close to the true ﬁnal state y at time T = 1. Here, 1 the velocity m(cid:126) represents a control variable, and Q is a diﬀerential operator ∇ ∇ (possibly Q = blkdiag(I, I) or Q = blkdiag( , )). The problem is solved on ∈ × ⊂ R a space-time grid ((cid:126)x, t) := ([x , x ], t) Ω [0, 1], where Ω 2 denotes the 1 2 domain occupied by the image. For the majority of the analysis presented in this paper we will consider the case δ = 0, i.e. whe(cid:90)re (cid:90) (cid:90) E 1 − β 1 (y, m(cid:126) ) = (y((cid:126)x, 1) y ((cid:126)x))2 dΩ + (Qm(cid:126) ((cid:126)x, t))2 dΩ dt, (2) 1 2γ 2 Ω 0 Ω however on a number of occasions we will describe modiﬁcations which are taken into account when δ is a positive parameter, measuring the deviation of y from the desired state y¯ during the entire time interval. The goal is to minimise the above energy subject to the continuity transport equation ∇ · y + (m(cid:126) y) = 0, (3) t with the initial condition y((cid:126)x, 0) = y as well as appropriate boundary con- 0 ditions, for instance periodic boundary conditions or Dirichlet conditions. Here, T m(cid:126) = [m , m ] is deﬁned for the two-dimensional domain Ω. While such a 1 2 problem can be found in many areas of sciences, we wish to apply the above for- mulation to the estimation of an optical ﬂow. To illustrate a particular set-up, examples for y and y are the two images shown in Fig. 11. 0 1 3. Discretisation using ﬁnite diﬀerences In this section, we wish to present how we discretise the optimisation prob- lem (2) with constraint (3). An outline is as follows: in ?? we examine the approach where such a PDE-constrained optimisation problem is discretised ﬁrst, upon which optimality conditions are found. In ?? we then extend this 1Images are taken from http://cs.brown.edu/~black/images.html. 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: The

text: optimal

text: transport

text: problem

text: The

text: examine

text: in

text: this

text: paper

text: of

text: minimising

text: the

text: functional

text: E

text: δ

text: (y,

text: y

text: dΩ

text: t)

text: dΩ

text: dt

text: 2γ

text: Ω

text: Ω

text: β

text: dΩ

text: dt,

text: Ω

text: where

text: β

text: and

text: γ

text: are

text: (positive)

text: parameters

text: that

text: can

text: be

text: understood

text: as

text: regulari-

text: sation

text: or

text: penalty

text: parameters.

text: The

text: parameter

text: γ

text: is

text: chosen

text: in

text: such

text: a

text: way

text: that

text: the

text: computed

text: state

text: is

text: close

text: to

text: the

text: true

text: ﬁnal

text: state

text: y

text: at

text: time

text: T

text: Here,

text: the

text: velocity

text: represents

text: a

text: control

text: variable,

text: and

text: Q

text: is

text: a

text: diﬀerential

text: operator

text: (possibly

text: Q

text: blkdiag(I,

text: I)

text: or

text: Q

text: blkdiag(

text: The

text: problem

text: is

text: solved

text: on

text: R

text: a

text: space-time

text: grid

text: t)

text: ([x

text: x

text: t)

text: Ω

text: where

text: Ω

text: denotes

text: the

text: domain

text: occupied

text: by

text: the

text: image.

text: For

text: the

text: majority

text: of

text: the

text: analysis

text: presented

text: in

text: this

text: paper

text: we

text: will

text: consider

text: the

text: case

text: δ

text: i.e.

text: E

text: β

text: (y,

text: y

text: dΩ

text: dΩ

text: dt,

text: 2γ

text: Ω

text: Ω

text: however

text: on

text: a

text: number

text: of

text: occasions

text: we

text: will

text: describe

text: modiﬁcations

text: which

text: are

text: taken

text: into

text: account

text: when

text: δ

text: is

text: a

text: positive

text: parameter,

text: measuring

text: the

text: deviation

text: of

text: y

text: from

text: the

text: desired

text: state

text: y¯

text: during

text: the

text: entire

text: time

text: interval.

text: The

text: goal

text: is

text: to

text: minimise

text: the

text: above

text: energy

text: subject

text: to

text: the

text: continuity

text: transport

text: equation

text: y

text: y)

text: t

text: with

text: the

text: initial

text: condition

text: y

text: as

text: well

text: as

text: appropriate

text: boundary

text: con-

text: ditions,

text: for

text: instance

text: periodic

text: boundary

text: conditions

text: or

text: Dirichlet

text: conditions.

text: Here,

text: T

text: [m

text: m

text: is

text: deﬁned

text: for

text: the

text: two-dimensional

text: domain

text: Ω.

text: While

text: such

text: a

text: problem

text: can

text: be

text: found

text: in

text: many

text: areas

text: of

text: sciences,

text: we

text: wish

text: to

text: apply

text: the

text: above

text: for-

text: mulation

text: to

text: the

text: estimation

text: of

text: an

text: optical

text: ﬂow.

text: To

text: illustrate

text: a

text: particular

text: set-up,

text: examples

text: for

text: y

text: and

text: y

text: are

text: the

text: two

text: images

text: shown

text: in

text: Fig.

text: Discretisation

text: using

text: ﬁnite

text: diﬀerences

text: In

text: this

text: section,

text: we

text: wish

text: to

text: present

text: how

text: we

text: discretise

text: the

text: optimisation

text: prob-

text: lem

text: with

text: constraint

text: An

text: outline

text: is

text: as

text: follows:

text: in

text: we

text: examine

text: the

text: approach

text: where

text: such

text: a

text: PDE-constrained

text: optimisation

text: problem

text: is

text: discretised

text: ﬁrst,

text: upon

text: which

text: optimality

text: conditions

text: are

text: found.

text: In

text: we

text: then

text: extend

text: this

text: are

text: taken

text: from

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text:   (cid:98)      A 0 0 0   y    0 A 0 0 m11 (cid:98) P = , (22) 1 0 0 A 0 m22 0 0 0 S (cid:101) (cid:98) where (cid:0) (cid:1) − (cid:98) − (cid:98) − S = C A 1BT + C A 1BT + C A 1BT ≈ y y My −m1 m1 mM1 m2 m2 m2 (cid:98) (C + ) A 1 BT + =: S. (cid:101) y 1 y y 2 Here, A is an approximation of the often highly singular matrix A , S is y My M generated by neglecting the oﬀ-diagonal terms in (1, 1) block, and , 1 2 (cid:98) are chosen such that M − M ≈ − − A 1 C A 1BT + C A 1BT . 1 y 2 m1 m1 m(cid:98)1 m2 m2 m2 We can of course construct analogous block triangular preconditioners. To ap- M M proximate the inverses of the sub-blocks of A , A , A , C + , BT + y m11 m22 y 1 y 2 within the preconditioner, it is reasonable to apply direct solvers as the matri- ces are typically relatively small and dense. It is of course possible to replace this with a multigrid, domain decomposition, or other iterative scheme, as an approximation of the constituent matrices. 6. Numerical results We now present the results of a number of numerical experiments, making use both of the ﬁnite diﬀerence discretisation outlined in ?? , and the radial basis function scheme of ?? . All experiments are implemented in Matlab. 6.1. Finite diﬀerence discretisation In our ﬁrst test we consider problem (2)–(3) and employ the Gauss-Newton scheme (5) in the ﬁnite diﬀerence setting. The parameters are chosen to be γ = 1 and Q = I. The regularisation parameter β is typically varied in our experiments. We compare the performance of the preconditioner presented in ?? and recall that the (1, 1)-block of the system matrix governing (5) is highly singular. We use the same discretisation level in time as we use for the spatial domain, and compare 5 spatial mesh levels for the synthetic data. For the image data we use ten time-steps and the same number of intermediate images. The × image data is as depicted in Fig. 1. We here use 100 100 pixel black and white images, where the values are scaled to be between zero and one. We choose the CGS method [36, Ch. 7.4.1] as the iterative scheme for the Gauss–Newton − system. This method is stopped when a certain tolerance (we use 10 6) for the relative residual norm of the linear system (5) is reached, starting from an all-zero initial guess. Notice that in Matlab’s implementation of CGS, the residual is measured in the Euclidean norm. The outer Gauss–Newton scheme is stopped once the relative Euclidean distance between consecutive iterates falls 22

text: A

text: y

text: A

text: P

text: A

text: S

text: where

text: S

text: C

text: A

text: C

text: A

text: C

text: A

text: y

text: y

text: My

text: (C

text: A

text: BT

text: S.

text: y

text: y

text: y

text: Here,

text: A

text: is

text: an

text: approximation

text: of

text: the

text: often

text: highly

text: singular

text: matrix

text: A

text: S

text: is

text: y

text: My

text: M

text: generated

text: by

text: neglecting

text: the

text: oﬀ-diagonal

text: terms

text: in

text: block,

text: and

text: are

text: chosen

text: such

text: that

text: M

text: M

text: A

text: C

text: A

text: C

text: A

text: y

text: We

text: can

text: of

text: course

text: construct

text: analogous

text: block

text: triangular

text: preconditioners.

text: To

text: ap-

text: M

text: M

text: proximate

text: the

text: inverses

text: of

text: the

text: sub-blocks

text: of

text: A

text: A

text: A

text: C

text: BT

text: y

text: y

text: y

text: within

text: the

text: preconditioner,

text: it

text: is

text: reasonable

text: to

text: apply

text: direct

text: solvers

text: as

text: the

text: matri-

text: ces

text: are

text: typically

text: relatively

text: small

text: and

text: dense.

text: It

text: is

text: of

text: course

text: possible

text: to

text: replace

text: this

text: with

text: a

text: multigrid,

text: domain

text: decomposition,

text: or

text: other

text: iterative

text: scheme,

text: as

text: an

text: approximation

text: of

text: the

text: constituent

text: matrices.

text: Numerical

text: results

text: We

text: now

text: present

text: the

text: results

text: of

text: a

text: number

text: of

text: numerical

text: experiments,

text: making

text: use

text: both

text: of

text: the

text: ﬁnite

text: diﬀerence

text: discretisation

text: outlined

text: in

text: and

text: the

text: radial

text: basis

text: function

text: scheme

text: of

text: All

text: experiments

text: are

text: implemented

text: in

text: Matlab.

text: Finite

text: diﬀerence

text: discretisation

text: In

text: our

text: ﬁrst

text: test

text: we

text: consider

text: problem

text: and

text: employ

text: the

text: Gauss-Newton

text: scheme

text: in

text: the

text: ﬁnite

text: diﬀerence

text: setting.

text: The

text: parameters

text: are

text: chosen

text: to

text: be

text: γ

text: and

text: Q

text: I.

text: The

text: regularisation

text: parameter

text: β

text: is

text: typically

text: varied

text: in

text: our

text: experiments.

text: We

text: compare

text: the

text: performance

text: of

text: the

text: preconditioner

text: presented

text: in

text: and

text: recall

text: that

text: the

text: of

text: the

text: system

text: matrix

text: governing

text: is

text: highly

text: singular.

text: We

text: use

text: the

text: same

text: discretisation

text: level

text: in

text: time

text: as

text: we

text: use

text: for

text: the

text: spatial

text: domain,

text: and

text: compare

text: spatial

text: mesh

text: levels

text: for

text: the

text: synthetic

text: data.

text: For

text: the

text: image

text: data

text: we

text: use

text: ten

text: time-steps

text: and

text: the

text: same

text: number

text: of

text: intermediate

text: images.

text: The

text: image

text: data

text: is

text: as

text: depicted

text: in

text: Fig.

text: We

text: here

text: use

text: pixel

text: black

text: and

text: white

text: images,

text: where

text: the

text: values

text: are

text: scaled

text: to

text: be

text: between

text: zero

text: and

text: one.

text: We

text: choose

text: the

text: CGS

text: method

text: Ch.

text: as

text: the

text: iterative

text: scheme

text: for

text: the

text: Gauss–Newton

text: system.

text: This

text: method

text: is

text: stopped

text: when

text: a

text: certain

text: tolerance

text: (we

text: use

text: for

text: the

text: relative

text: residual

text: norm

text: of

text: the

text: linear

text: system

text: is

text: reached,

text: starting

text: from

text: an

text: all-zero

text: initial

text: guess.

text: Notice

text: that

text: in

text: Matlab’s

text: implementation

text: of

text: CGS,

text: the

text: residual

text: is

text: measured

text: in

text: the

text: Euclidean

text: norm.

text: The

text: outer

text: Gauss–Newton

text: scheme

text: is

text: stopped

text: once

text: the

text: relative

text: Euclidean

text: distance

text: between

text: consecutive

text: iterates

text: falls


text: (a) Computed state at time step 5 (b) Computed control at time step 5 10-1 10-2 60 10-3 40 20 1 2 3 4 Gauss-Newton step (c) Varying δ Figure 5: Results for the preconditioned iteration for the optical ﬂow problem. We show an instance of the control and the state as well as the number of CGS iterations per Gauss– Newton step for varying regularisation parameter δ. our next test problem, we provide a proof of concept that the methodology can be applied to dense matrix systems arising from Gaussian basis functions. We therefore select RBF centres using the superpixels computed using the initial image from Fig. 3, and take the desired state to be a greyscale linear mapping, over the time variable, between this and the target image from the same ﬁgure. ∇ ∇ Within the cost functional (1), we take γ = 1 and Q = blkdiag( , ). We test a range of values of δ and β, as well as time-steps τ = 0.1 and τ = 0.05 within the time interval [0, 1]. In each case we apply outer (Gauss–Newton) iteration to a − tolerance of 10 2 for the relative distance between new and old solution, and use a Gmres method preconditioned by P (as described in ?? ; see (22)) to 1 solve the matrix systems obtained from the outer iteration. Our Krylov solver − is run to a tolerance of 10 4. As before, all norms are Euclidean in Matlab’s implementation. The lowest number of outer iterations required for convergence was three, so to measure the eﬀectiveness of the Gmres solver we present the 24 snoitareti fo rebmun ##LTFigure## ##LTFigure## ##LTFigure##

text: (a)

text: Computed

text: state

text: at

text: time

text: step

text: (b)

text: Computed

text: control

text: at

text: time

text: step

font: default

text: Gauss-Newton

text: step

text: (c)

text: Varying

text: δ

text: Figure

text: Results

text: for

text: the

text: preconditioned

text: iteration

text: for

text: the

text: optical

text: ﬂow

text: problem.

text: We

text: show

text: an

text: instance

text: of

text: the

text: control

text: and

text: the

text: state

text: as

text: well

text: as

text: the

text: number

text: of

text: CGS

text: iterations

text: per

text: Gauss–

text: Newton

text: step

text: for

text: varying

text: regularisation

text: parameter

text: δ.

text: our

text: next

text: test

text: problem,

text: we

text: provide

text: a

text: proof

text: of

text: concept

text: that

text: the

text: methodology

text: can

text: be

text: applied

text: to

text: dense

text: matrix

text: systems

text: arising

text: from

text: Gaussian

text: basis

text: functions.

text: We

text: therefore

text: select

text: RBF

text: centres

text: using

text: the

text: superpixels

text: computed

text: using

text: the

text: initial

text: image

text: from

text: Fig.

text: and

text: take

text: the

text: desired

text: state

text: to

text: be

text: a

text: greyscale

text: linear

text: mapping,

text: over

text: the

text: time

text: variable,

text: between

text: this

text: and

text: the

text: target

text: image

text: from

text: the

text: same

text: ﬁgure.

text: Within

text: the

text: cost

text: functional

text: we

text: take

text: γ

text: and

text: Q

text: blkdiag(

text: We

text: test

text: a

text: range

text: of

text: values

text: of

text: δ

text: and

text: β,

text: as

text: well

text: as

text: time-steps

text: τ

text: and

text: τ

text: within

text: the

text: time

text: interval

text: In

text: each

text: case

text: we

text: apply

text: outer

text: (Gauss–Newton)

text: iteration

text: to

text: a

text: tolerance

text: of

text: for

text: the

text: relative

text: distance

text: between

text: new

text: and

text: old

text: solution,

text: and

text: use

text: a

text: Gmres

text: method

text: preconditioned

text: by

text: P

text: (as

text: described

text: in

text: see

text: to

text: solve

text: the

text: matrix

text: systems

text: obtained

text: from

text: the

text: outer

text: iteration.

text: Our

text: Krylov

text: solver

text: is

text: run

text: to

text: a

text: tolerance

text: of

text: As

text: before,

text: all

text: norms

text: are

text: Euclidean

text: in

text: Matlab’s

text: implementation.

text: The

text: lowest

text: number

text: of

text: outer

text: iterations

text: required

text: for

text: convergence

text: was

text: three,

text: so

text: to

text: measure

text: the

text: eﬀectiveness

text: of

text: the

text: Gmres

text: solver

text: we

text: present

text: the

text: snoitareti

text: fo

text: rebmun

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: Acoustic boundary layers as boundary conditions Martin Berggren∗, Anders Bernland, Daniel Noreland Department of Computing Science, Umeå University, Sweden May 30, 2020 Abstract The linearized, compressible Navier–Stokes equations can be used to model acoustic wave prop- agation in the presence of viscous and thermal boundary layers. However, acoustic boundary layers are notorious for invoking prohibitively high resolution requirements on numerical solutions of the equations. We derive and present a strategy for how viscous and thermal boundary-layer eﬀects can be represented as a boundary condition on the standard Helmholtz equation for the acoustic pressure. This boundary condition constitutes an perturbation, where is the boundary-layer thickness, of the 𝑂(𝛿) 𝛿 vanishing Neumann condition for the acoustic pressure associated with a lossless sound-hard wall. The approximate model is valid when the wavelength and the minimum radius of curvature of the wall is much larger than the boundary layer thickness. In the special case of sound propagation in a cylindrical duct, the model collapses to the classical Kirchhoﬀ solution. We assess the model in the case of sound propagation through a compression driver, a kind of transducer that is commonly used to feed horn loudspeakers. Due to the presence of shallow chambers and thin slits in the device, it is crucial to include modeling of visco–thermal losses in the acoustic analysis. The transmitted power spectrum through the device calculated numerically using our model agrees well with computations using a hybrid model, where the full linearized, compressible Navier–Stokes equations are solved in the narrow regions of the device and the inviscid Helmholtz equations elsewhere. However, our model needs almost two orders of magnitude less memory and computational time than the more complete model. Keywords: acoustics; visco–thermal boundary layers; Helmholtz equation; Wentzell boundary condition, compression driver 1 Background The classical wave equation and its time harmonic counterpart, the Helmholtz equation, provide accurate mathematical models for acoustic wave propagation under a wide range of conditions. Eﬀects that are not accounted for in the linear regime are mainly related to various loss mechanisms, manifested in two diﬀerent ways. On the one hand there is bulk loss, which is a consequence of bulk shear, heat conduction and molecular exchange of energy. Bulk losses are small and have in general an appreciable eﬀect only for propagation over long distances [8, § 6.4]. Boundary eﬀects, on the other hand, are due to heat exchange with walls and viscous dissipation owing to the shear motion caused by the contact or non-slip boundary condition at the wall boundary. The relative importance of the thermal and viscous losses varies with the type of medium, the wavelength, and the characteristic size of the domain. In air, thermal and viscous boundary eﬀects are of the same order of magnitude at audio frequencies, since the Prantl number for air is close to unity. For devices such as hearing aids, microphones, and micro-loudspeakers, these eﬀects can have a great inﬂuence on the generated or detected sound power level. Another type of devices that often cannot be modeled with suﬃcient accuracy ∗Corresponding author 1 ##LTLine##

text: Acoustic

label: title

font: ZNEFIL+STIXGeneral-Regular

text: boundary

text: layers

text: as

text: boundary

text: conditions

text: Martin

label: author

text: Berggren∗,

text: Anders

text: Bernland,

text: Daniel

text: Noreland

text: Department

font: SPYZCP+STIXGeneral-Italic

text: of

text: Computing

text: Science,

text: Umeå

text: University,

text: Sweden

text: May

text: Abstract

font: OQGLKQ+STIXGeneral-Bold

text: The

label: abstract

text: linearized,

text: compressible

text: Navier–Stokes

text: equations

text: can

text: be

text: used

text: to

text: model

text: acoustic

text: wave

text: prop-

text: agation

text: in

text: the

text: presence

text: of

text: viscous

text: and

text: thermal

text: boundary

text: layers.

text: However,

text: acoustic

text: boundary

text: layers

text: are

text: notorious

text: for

text: invoking

text: prohibitively

text: high

text: resolution

text: requirements

text: on

text: numerical

text: solutions

text: of

text: the

text: equations.

text: We

text: derive

text: and

text: present

text: a

text: strategy

text: for

text: how

text: viscous

text: and

text: thermal

text: boundary-layer

text: eﬀects

text: can

text: be

text: represented

text: as

text: a

text: boundary

text: condition

text: on

text: the

text: standard

text: Helmholtz

text: equation

text: for

text: the

text: acoustic

text: pressure.

text: This

text: boundary

text: condition

text: constitutes

text: an

text: perturbation,

text: where

text: is

text: the

text: boundary-layer

text: thickness,

text: of

text: the

text: 𝑂(𝛿)

text: 𝛿

text: vanishing

text: Neumann

text: condition

text: for

text: the

text: acoustic

text: pressure

text: associated

text: with

text: a

text: lossless

text: sound-hard

text: wall.

text: The

text: approximate

text: model

text: is

text: valid

text: when

text: the

text: wavelength

text: and

text: the

text: minimum

text: radius

text: of

text: curvature

text: of

text: the

text: wall

text: is

text: much

text: larger

text: than

text: the

text: boundary

text: layer

text: thickness.

text: In

text: the

text: special

text: case

text: of

text: sound

text: propagation

text: in

text: a

text: cylindrical

text: duct,

text: the

text: model

text: collapses

text: to

text: the

text: classical

text: Kirchhoﬀ

text: solution.

text: We

text: assess

text: the

text: model

text: in

text: the

text: case

text: of

text: sound

text: propagation

text: through

text: a

text: compression

text: driver,

text: a

text: kind

text: of

text: transducer

text: that

text: is

text: commonly

text: used

text: to

text: feed

text: horn

text: loudspeakers.

text: Due

text: to

text: the

text: presence

text: of

text: shallow

text: chambers

text: and

text: thin

text: slits

text: in

text: the

text: device,

text: it

text: is

text: crucial

text: to

text: include

text: modeling

text: of

text: visco–thermal

text: losses

text: in

text: the

text: acoustic

text: analysis.

text: The

text: transmitted

text: power

text: spectrum

text: through

text: the

text: device

text: calculated

text: numerically

text: using

text: our

text: model

text: agrees

text: well

text: with

text: computations

text: using

text: a

text: hybrid

text: model,

text: where

text: the

text: full

text: linearized,

text: compressible

text: Navier–Stokes

text: equations

text: are

text: solved

text: in

text: the

text: narrow

text: regions

text: of

text: the

text: device

text: and

text: the

text: inviscid

text: Helmholtz

text: equations

text: elsewhere.

text: However,

text: our

text: model

text: needs

text: almost

text: two

text: orders

text: of

text: magnitude

text: less

text: memory

text: and

text: computational

text: time

text: than

text: the

text: more

text: complete

text: model.

text: Keywords:

text: acoustics;

text: visco–thermal

text: boundary

text: layers;

text: Helmholtz

text: equation;

text: Wentzell

text: boundary

text: condition,

text: compression

text: driver

text: Background

text: The

text: classical

text: wave

text: equation

text: and

text: its

text: time

text: harmonic

text: counterpart,

text: the

text: Helmholtz

text: equation,

text: provide

text: accurate

text: mathematical

text: models

text: for

text: acoustic

text: wave

text: propagation

text: under

text: a

text: wide

text: range

text: of

text: conditions.

text: Eﬀects

text: that

text: are

text: not

text: accounted

text: for

text: in

text: the

text: linear

text: regime

text: are

text: mainly

text: related

text: to

text: various

text: loss

text: mechanisms,

text: manifested

text: in

text: two

text: diﬀerent

text: ways.

text: On

text: the

text: one

text: hand

text: there

text: is

text: bulk

text: loss,

text: which

text: is

text: a

text: consequence

text: of

text: bulk

text: shear,

text: heat

text: conduction

text: and

text: molecular

text: exchange

text: of

text: energy.

text: Bulk

text: losses

text: are

text: small

text: and

text: have

text: in

text: general

text: an

text: appreciable

text: eﬀect

text: only

text: for

text: propagation

text: over

text: long

text: distances

text: Boundary

text: eﬀects,

text: on

text: the

text: other

text: hand,

text: are

text: due

text: to

text: heat

text: exchange

text: with

text: walls

text: and

text: viscous

text: dissipation

text: owing

text: to

text: the

text: shear

text: motion

text: caused

text: by

text: the

text: contact

text: or

text: non-slip

text: boundary

text: condition

text: at

text: the

text: wall

text: boundary.

text: The

text: relative

text: importance

text: of

text: the

text: thermal

text: and

text: viscous

text: losses

text: varies

text: with

text: the

text: type

text: of

text: medium,

text: the

text: wavelength,

text: and

text: the

text: characteristic

text: size

text: of

text: the

text: domain.

text: In

text: air,

text: thermal

text: and

text: viscous

text: boundary

text: eﬀects

text: are

text: of

text: the

text: same

text: order

text: of

text: magnitude

text: at

text: audio

text: frequencies,

text: since

text: the

text: Prantl

text: number

text: for

text: air

text: is

text: close

text: to

text: unity.

text: For

text: devices

text: such

text: as

text: hearing

text: aids,

text: microphones,

text: and

text: micro-loudspeakers,

text: these

text: eﬀects

text: can

text: have

text: a

text: great

text: inﬂuence

text: on

text: the

text: generated

text: or

text: detected

text: sound

text: power

text: level.

text: Another

text: type

text: of

text: devices

text: that

text: often

text: cannot

text: be

text: modeled

text: with

text: suﬃcient

text: accuracy

text: ∗Corresponding

text: author

text: ##LTLine##


text: 𝜈 𝜈′ (58) 𝑁Pr = 𝑐 𝜌 = 𝛾 𝑃 0 𝜅 𝜅′ is about unity and approximately constant over a wide temperature range. Thus, for such gases, we may safely assume that and both are similarly small. Outside of a thin layer close to the wall, the terms 𝜈′ 𝜅′ involving the viscosity and thermal conductivity parameter become small, and it becomes reasonable to replace system (57) with the isentropic equations (8). System (57) can be solved exactly, subject to boundary conditions (10) a and matching conditions for all variables as to an exterior isentropic solution to system (8) evaluated at a position 𝑦 → +∞ 𝑦 = 𝑦 close to the wall but outside the boundary layer. We will denote these limiting values by , 𝛿, 𝒖∞(𝒓) 𝑝∞(𝒓) and so on. 𝜌∞(𝒓) Equation (57c) simply implies that the pressure is constant in the vertical direction across the boundary layer, 𝑝(𝒓, 𝑦) = 𝑝∞(𝒓) ∀𝑦 > 0. (59) Moreover, the tangential components of equation (8) evaluated at are 𝑦 = 𝑦 𝛿 i𝜔𝜌 𝒖∞ + ∇T𝑝∞ = 0. (60) 0 Substituting equations (59) and (60) into equation (57b), we can formulate the boundary-value problem i𝜔𝒖 − 𝜈 𝜕2𝒖 − i𝜔𝒖∞ = 𝟎, (61a) 𝜕𝑦2 𝒖| = 𝟎, (61b) 𝑦=0 lim 𝒖 = 𝒖∞, (61c) 𝑦→+∞ which has the solution 𝒖 = 𝒖∞(𝒓) (1 − e−(1+i)𝑦∕𝛿𝑉 ) , (62) where √ 2𝜈 (63) 𝛿 = , 𝑉 𝜔 is the viscous boundary-layer thickness. The remaining two equations (57a) and (57d) combine into i𝜔𝜌 𝑐 𝑇 − i𝜔𝑝0𝜌 − 𝜅 𝜕2𝑇 = 0. (64) 0 𝑉 𝜌0 𝜕𝑦2 Dividing equation (64) with and rewriting it in several steps, we ﬁnd that 𝑇 0 20 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: 𝜈

font: PGZLFD+STIXMath-Italic

text: 𝜈′

text: 𝑁Pr

font: LEXSTI+STIXMath-Regular

text: 𝑐

text: 𝜌

text: 𝛾

text: 𝑃

text: 𝜅

text: 𝜅′

text: is

text: about

text: unity

text: and

text: approximately

text: constant

text: over

text: a

text: wide

text: temperature

text: range.

text: Thus,

text: for

text: such

text: gases,

text: we

text: may

text: safely

text: assume

text: that

text: and

text: both

text: are

text: similarly

text: small.

text: Outside

text: of

text: a

text: thin

text: layer

text: close

text: to

text: the

text: wall,

text: the

text: terms

text: 𝜈′

text: 𝜅′

text: involving

text: the

text: viscosity

text: and

text: thermal

text: conductivity

text: parameter

text: become

text: small,

text: and

text: it

text: becomes

text: reasonable

text: to

text: replace

text: system

text: with

text: the

text: isentropic

text: equations

text: System

text: can

text: be

text: solved

text: exactly,

text: subject

text: to

text: boundary

text: conditions

text: a

text: and

text: matching

text: conditions

text: for

text: all

text: variables

text: as

text: to

text: an

text: exterior

text: isentropic

text: solution

text: to

text: system

text: evaluated

text: at

text: a

text: position

text: 𝑦

text: 𝑦

text: 𝑦

text: close

text: to

text: the

text: wall

text: but

text: outside

text: the

text: boundary

text: layer.

text: We

text: will

text: denote

text: these

text: limiting

text: values

text: by

text: 𝛿,

text: 𝒖∞(𝒓)

text: 𝑝∞(𝒓)

text: and

text: so

text: on.

text: 𝜌∞(𝒓)

text: Equation

text: simply

text: implies

text: that

text: the

text: pressure

text: is

text: constant

text: in

text: the

text: vertical

text: direction

text: across

text: the

text: boundary

text: layer,

text: 𝑝(𝒓,

text: 𝑦)

text: 𝑝∞(𝒓)

text: ∀𝑦

text: Moreover,

text: the

text: tangential

text: components

text: of

text: equation

text: evaluated

text: at

text: are

text: 𝑦

text: 𝑦

text: 𝛿

text: i𝜔𝜌

text: 𝒖∞

text: ∇T𝑝∞

text: Substituting

text: equations

text: and

text: into

text: equation

text: we

text: can

text: formulate

text: the

text: boundary-value

text: problem

text: i𝜔𝒖

text: 𝜈

text: 𝜕2𝒖

text: i𝜔𝒖∞

text: 𝟎,

text: 𝜕𝑦2

text: 𝒖|

text: 𝟎,

text: lim

text: 𝒖

text: 𝒖∞,

text: 𝑦→+∞

text: which

text: has

text: the

text: solution

text: 𝒖

text: 𝒖∞(𝒓)

text: where

text: 2𝜈

text: 𝛿

text: 𝑉

text: 𝜔

text: is

text: the

text: viscous

text: boundary-layer

text: thickness.

text: The

text: remaining

text: two

text: equations

text: and

text: combine

text: into

text: i𝜔𝜌

text: 𝑐

text: 𝑇

text: i𝜔𝑝0𝜌

text: 𝜅

text: 𝜕2𝑇

text: 𝑉

text: 𝜌0

text: 𝜕𝑦2

text: Dividing

text: equation

text: with

text: and

text: rewriting

text: it

text: in

text: several

text: steps,

text: we

text: ﬁnd

text: that

text: 𝑇

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [( ) ( )] Re 1 − 3i 𝑎(𝑝̄, 𝑝) + 2𝑘 ‖𝑝‖2 2 0 𝐿2(Ω) ∫ ∫ ∫ ∫ ∫ 3 1 1 = |∇𝑝|2 + 𝑘2 |𝑝|2 + 𝑘 |𝑝|2 + 𝛿 (𝛾 − 1)𝑘2 |𝑝|2 + 𝛿 |∇T𝑝|2. (75) 0 2 0 4 𝑇 0 4 𝑉 ≥ Ω Ω Γio Γw Γw 1 ‖𝑝‖2 , 4 𝑊 which together with inequality ≤ [( ) ( )] Re 1 − 32i 𝑎(𝑝̄, 𝑝) + 2𝑘0‖𝑝‖2𝐿2(Ω) ||||1 − 32i|||| |||𝑎(𝑝̄, 𝑝) + 2𝑘0‖𝑝‖2𝐿2(Ω)||| (76) √ 13 | | = |𝑎(𝑝̄, 𝑝) + 2𝑘 ‖𝑝‖2 | 2 | 0 𝐿2(Ω)| yields the conclusion. Lemma B.2 (Injectivity). For each 𝑘 > 0, if 𝑝 ∈ 𝑊 such that 0 (77) 𝑎(𝑞, 𝑝) = 0 ∀𝑞 ∈ 𝑊 , ≡ then 𝑝 0. If satisﬁes equation (77), then Proof. 𝑝 ∈ 𝑊 ∫ ∫ ∫ Im 𝑎(𝑝̄, 𝑝) = 𝑘 |𝑝|2 + 𝛿 𝑘2 𝛾 − 1 |𝑝|2 + 𝛿 1 |∇T𝑝|2 = 0, (78) 0 𝑇 0 2 𝑉 2 Γio Γ Γ 𝑤 𝑤 which means that the trace of on vanishes, that is, . Let be an open extension of 𝑝 𝜕Ω 𝑝 ∈ 𝐻1(Ω) Ω̂ Ω 0 in which is compactly embedded; that is, is open, bounded, and connected such that . Ω Ω̂ ∈ ℝ3 Ω ⊂ Ω̂ Since and satisﬁes equation (77), we may extend it by zero into a that, for 𝑝 ∈ 𝐻1(Ω) ⊂ 𝑊 𝑝 ∈ 𝐻1(Ω̂ ) 0 each open set compactly embedded into ( ), satisﬁes 𝐾 Ω̂ 𝐾 ⊂ Ω̂ ∫ ∫ −𝑘2 𝑞𝑝 + ∇𝑞 ⋅ ∇𝑝 = 0 ∀𝑞 ∈ 𝒞∞(𝐾), (79) 0 0 Ω Ω which implies that −𝑘2𝑝 − Δ𝑝 = 0 almost everywhere in 𝐾. (80) 0 Since the extended satisﬁes property (80) an≡d vanishes identically in the open set , the unique 𝑝 Ω̂ ⧵ Ω continuation principle [7, Ch. 4.3] implies that in . 𝑝 0 Ω Lemma B.1 and B.2 then imply that Theorem B.3. Problem (72) has a unique solution for each 𝑘 > 0. 0 23 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: EIMKHM+STIXMathExtensions-Regular

text: Re

text: 𝑎(𝑝̄,

text: 𝑝)

text: 2𝑘

text: ‖𝑝‖2

font: DRIPPK+STIXMathCalligraphy-Regular

text: 𝑘2

text: 𝑘

text: 𝛿

text: (𝛾

text: 𝛿

text: 𝑇

text: 𝑉

text: Ω

text: Ω

text: Γio

text: Γw

text: Γw

text: ‖𝑝‖2

text: 𝑊

text: which

text: together

text: with

text: inequality

text: Re

text: 𝑎(𝑝̄,

text: 𝑝)

text: 2𝑘0‖𝑝‖2𝐿2(Ω)

text: |||𝑎(𝑝̄,

text: 𝑝)

text: |𝑎(𝑝̄,

text: 𝑝)

text: 2𝑘

text: ‖𝑝‖2

text: yields

text: the

text: conclusion.

text: Lemma

text: (Injectivity).

text: For

text: each

text: 𝑘

text: if

text: 𝑝

text: 𝑊

text: such

text: that

text: 𝑎(𝑞,

text: 𝑝)

text: ∀𝑞

text: 𝑊

text: then

text: 𝑝

text: If

text: satisﬁes

text: equation

text: then

text: Proof.

text: 𝑝

text: 𝑊

text: Im

text: 𝑎(𝑝̄,

text: 𝑝)

text: 𝑘

text: 𝛿

text: 𝑘2

text: 𝛾

text: 𝛿

text: 𝑇

text: 𝑉

text: Γio

text: Γ

text: Γ

text: 𝑤

text: 𝑤

text: which

text: means

text: that

text: the

text: trace

text: of

text: on

text: vanishes,

text: that

text: is,

text: Let

text: be

text: an

text: open

text: extension

text: of

text: 𝑝

text: 𝜕Ω

text: 𝑝

text: Ω̂

text: Ω

text: in

text: which

text: is

text: compactly

text: embedded;

text: that

text: is,

text: is

text: open,

text: bounded,

text: and

text: connected

text: such

text: that

text: Ω

text: Ω̂

text: ℝ3

text: Ω

text: Ω̂

text: Since

text: and

text: satisﬁes

text: equation

text: we

text: may

text: extend

text: it

text: by

text: zero

text: into

text: a

text: that,

text: for

text: 𝑝

text: 𝑊

text: 𝑝

text: 𝐻1(Ω̂

text: each

text: open

text: set

text: compactly

text: embedded

text: into

text: satisﬁes

text: 𝐾

text: Ω̂

text: 𝐾

text: Ω̂

text: −𝑘2

text: 𝑞𝑝

text: ∇𝑞

text: ∇𝑝

text: ∀𝑞

text: 𝒞∞(𝐾),

text: Ω

text: Ω

text: which

text: implies

text: that

text: −𝑘2𝑝

text: Δ𝑝

text: almost

text: everywhere

text: in

text: 𝐾.

text: Since

text: the

text: extended

text: satisﬁes

text: property

text: an≡d

text: vanishes

text: identically

text: in

text: the

text: open

text: set

text: the

text: unique

text: 𝑝

text: Ω̂

text: Ω

text: continuation

text: principle

text: Ch.

text: implies

text: that

text: in

text: 𝑝

text: Ω

text: Lemma

text: and

text: then

text: imply

text: that

text: Theorem

text: Problem

text: has

text: a

text: unique

text: solution

text: for

text: each

text: 𝑘

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##