text: 17 days) and the highest mean charge ($210806). Similarly to the severity of illness, patients with highest risk to die has the longest mean LOS (almost 15 days) and highest mean charge ($200746). Descriptive statistics of SPARCS 2013 with respect to the chosen covariates are presented in Table 3.1. Table 3.1: Descriptive statistics of SPARCS 2013 (SET 1) Characteristics Group N(%) Sample N(%) LOS(SD) Sample LOS(SD) Charge(SD) Sample Charge(SD) All Patients 2418874(100) 5000(100) 5.46(8.11) 5.51(8.16) 36931.77(68973.47) 36861.8(67053.64) MDC 0.0 17.0(0.0) 11.0(24.69) 102910.82(280754.64) 1.0 142651.0(5.9) 298.0(5.96) 5.7(8.69) 5.01(6.14) 46962.08(83724.59) 41911.53(50501.65) 2.0 4138.0(0.17) 13.0(0.26) 3.62(5.18) 3.38(1.89) 27185.04(37576.18) 28478.72(22611.85) 3.0 32743.0(1.35) 72.0(1.44) 3.59(5.59) 2.81(2.72) 29468.92(50592.3) 22093.15(20516.67) 4.0 206374.0(8.53) 425.0(8.5) 5.81(7.64) 5.42(6.99) 37165.6(64478.26) 35254.34(48416.02) 5.0 320765.0(13.26) 655.0(13.1) 4.78(6.58) 4.68(5.4) 50065.14(84839.8) 48514.49(67896.89) 6.0 211325.0(8.74) 461.0(9.22) 5.11(6.63) 5.56(7.16) 35785.32(54820.39) 37176.32(45615.65) 7.0 65928.0(2.73) 116.0(2.32) 5.6(6.96) 4.91(4.31) 42718.49(78816.64) 34176.78(38341.19) 8.0 201134.0(8.32) 419.0(8.38) 4.91(5.95) 5.0(5.35) 50655.45(55819.15) 50609.01(45334.44) 9.0 66120.0(2.73) 136.0(2.72) 4.6(5.95) 5.07(8.42) 28073.74(37308.49) 28829.12(29869.57) 10.0 74993.0(3.1) 171.0(3.42) 3.97(5.83) 4.05(4.72) 28568.47(43837.41) 27236.6(30456.03) 11.0 103597.0(4.28) 221.0(4.42) 5.43(6.75) 5.09(5.1) 36812.91(53368.81) 33884.47(38131.54) 12.0 11181.0(0.46) 21.0(0.42) 3.44(6.27) 4.81(10.56) 30593.31(30945.72) 39233.29(46533.28) 13.0 31682.0(1.31) 57.0(1.14) 3.13(5.23) 2.47(2.03) 28998.31(33592.18) 31389.63(20325.52) 14.0 257203.0(10.63) 504.0(10.08) 2.91(2.54) 2.88(2.47) 16435.92(17226.17) 16714.7(18104.7) 15.0 236599.0(9.78) 439.0(8.78) 3.78(7.99) 4.06(7.8) 17912.83(85865.5) 18682.72(72830.49) 16.0 37899.0(1.57) 92.0(1.84) 5.01(6.87) 4.77(3.79) 37100.38(83604.25) 36537.56(52336.47) 17.0 22289.0(0.92) 55.0(1.1) 9.57(12.73) 9.38(11.59) 87130.44(139632.35) 81519.0(128268.96) 18.0 108416.0(4.48) 224.0(4.48) 9.09(10.7) 10.24(15.07) 63423.77(99592.33) 80804.11(200106.77) 19.0 116683.0(4.82) 245.0(4.9) 12.94(16.11) 12.62(17.7) 34162.28(57058.45) 32507.77(49653.33) 20.0 75432.0(3.12) 170.0(3.4) 6.34(7.45) 6.6(7.65) 17400.15(23797.61) 17228.44(20575.0) 21.0 30203.0(1.25) 71.0(1.42) 4.29(7.18) 4.77(10.44) 31248.52(64435.64) 33845.59(75320.46) 22.0 1929.0(0.08) 2.0(0.04) 9.06(13.5) 8.0(2.83) 79337.2(184652.6) 51080.31(29187.33) 23.0 46924.0(1.94) 106.0(2.12) 10.87(10.27) 11.18(8.88) 46721.27(52350.27) 45356.56(37999.3) 24.0 8733.0(0.36) 20.0(0.4) 8.6(11.36) 8.55(8.81) 57383.57(105543.15) 40839.06(39649.57) 25.0 3916.0(0.16) 7.0(0.14) 10.77(12.01) 11.0(7.44) 103841.73(118285.21) 73790.14(54114.8) Severity 0.0 40.0(0.0) 6.35(16.4) 47710.78(186214.68) 1.0 881300.0(36.43) 1760.0(35.2) 3.09(3.97) 3.02(3.37) 20164.74(25917.49) 20249.04(23995.3) 2.0 929347.0(38.42) 1939.0(38.78) 4.96(6.89) 5.16(7.76) 30512.25(37884.57) 30602.25(38507.07) 3.0 479712.0(19.83) 1048.0(20.96) 7.73(8.46) 7.57(7.68) 51935.05(65352.31) 51307.28(61645.27) 4.0 128475.0(5.31) 253.0(5.06) 16.83(18.2) 17.06(18.36) 142361.38(210806.88) 140564.83(210012.56) Mortality Extreme 106154.0(4.39) 210(4.2) 14.96(16.66) 13.81(15.11) 129939.83(200746.65) 114408.34(172257.11) Major 311482.0(12.88) 692(13.84) 8.69(10.14) 8.51(9.96) 61247.22(92604.92) 64073.56(108815.34) Minor 1482115.0(61.27) 3007(60.14) 4.03(6.16) 4.02(6.31) 24133.09(33016.21) 23905.06(31377.21) Moderate 519083.0(21.46) 1091(21.82) 5.67(7.03) 6.12(7.96) 39863.27(55375.06) 40386.64(51083.0) 3.2.2 Estimation of RGRST Regression Model Due to the huge data size and limited computation power, our estimation is based on a subset with size 5000 of SPARCS 2013 obtained through uniform random sampling. Descriptive statistics of the samples are summarized in Tables 3.1, (Sample is used to indicate the statistics computed for samples). Through direct comparison of statistics computed for samples and for the entire database, we ﬁnd that our samples copy the statistical properties of the entire database quite well. After preliminary goodness-of-ﬁt analyses, the RGRST model we ﬁnally choose for regression has only one component appearing in the convext com- bination in Equation 3.3 and the corresponding dimension of Phase-Type tran- sition matrix is 1 as well. That means only three parameters are needed to characterize the underlying RGRST process, two for the log-normal component (µ and σ) and one for the Phase-Type component (s). Later, we will call this model RGRST (1:1) with the ﬁrst “1” representing the number of summand in Equation 3.3 and the second “1” denoting the dimension of the corresponding Phase-Type component. The ﬁtting result for both of the marginal and joint densities of log-charge (ζYT ) and LOS (eζT )3 are plotted in Figure 3.2 and 3.3, where the estimated value of (µ, σ, s) equals to (2.96, 0.81, 0.02). The ﬁtting statistics we consider here is the Pearson’s Chi-square, the Chi-square statis- (cid:16) (cid:17) (cid:0) (cid:1) 3exp ζYT and exp ζT are given as in 2.10 which are just a re-scale of charge and LOS with the scale deter- mined by the value of explanatory vairables through regression equation 2.11. 13 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: days)

text: and

text: the

text: highest

text: mean

text: charge

text: Similarly

text: to

text: the

text: severity

text: of

text: illness,

text: patients

text: with

text: highest

text: risk

text: to

text: die

text: has

text: the

text: longest

text: mean

text: LOS

text: (almost

text: days)

text: and

text: highest

text: mean

text: charge

text: Descriptive

text: statistics

text: of

text: SPARCS

text: with

text: respect

text: to

text: the

text: chosen

text: covariates

text: are

text: presented

text: in

text: Table

text: Table

text: Descriptive

text: statistics

text: of

text: SPARCS

text: (SET

text: Characteristics

text: Group

text: N(%)

text: Sample

text: N(%)

text: LOS(SD)

text: Sample

text: LOS(SD)

text: Charge(SD)

text: Sample

text: Charge(SD)

text: All

text: Patients

text: MDC

text: Severity

text: Mortality

text: Extreme

text: Major

text: Minor

text: Moderate

text: Estimation

text: of

text: RGRST

text: Regression

text: Model

text: Due

text: to

text: the

text: huge

text: data

text: size

text: and

text: limited

text: computation

text: power,

text: our

text: estimation

text: is

text: based

text: on

text: a

text: subset

text: with

text: size

text: of

text: SPARCS

text: obtained

text: through

text: uniform

text: random

text: sampling.

text: Descriptive

text: statistics

text: of

text: the

text: samples

text: are

text: summarized

text: in

text: Tables

text: (Sample

text: is

text: used

text: to

text: indicate

text: the

text: statistics

text: computed

text: for

text: samples).

text: Through

text: direct

text: comparison

text: of

text: statistics

text: computed

text: for

text: samples

text: and

text: for

text: the

text: entire

text: database,

text: we

text: ﬁnd

text: that

text: our

text: samples

text: copy

text: the

text: statistical

text: properties

text: of

text: the

text: entire

text: database

text: quite

text: well.

text: After

text: preliminary

text: goodness-of-ﬁt

text: analyses,

text: the

text: RGRST

text: model

text: we

text: ﬁnally

text: choose

text: for

text: regression

text: has

text: only

text: one

text: component

text: appearing

text: in

text: the

text: convext

text: com-

text: bination

text: in

text: Equation

text: and

text: the

text: corresponding

text: dimension

text: of

text: Phase-Type

text: tran-

text: sition

text: matrix

text: is

text: as

text: well.

text: That

text: means

text: only

text: three

text: parameters

text: are

text: needed

text: to

text: characterize

text: the

text: underlying

text: RGRST

text: process,

text: two

text: for

text: the

text: log-normal

text: component

text: (µ

text: and

text: σ)

text: and

text: one

text: for

text: the

text: Phase-Type

text: component

text: (s).

text: Later,

text: we

text: will

text: call

text: this

text: model

text: RGRST

text: with

text: the

text: ﬁrst

text: “1”

text: representing

text: the

text: number

text: of

text: summand

text: in

text: Equation

text: and

text: the

text: second

text: “1”

text: denoting

text: the

text: dimension

text: of

text: the

text: corresponding

text: Phase-Type

text: component.

text: The

text: ﬁtting

text: result

text: for

text: both

text: of

text: the

text: marginal

text: and

text: joint

text: densities

text: of

text: log-charge

text: (ζYT

text: and

text: LOS

text: (eζT

text: are

text: plotted

text: in

text: Figure

text: and

text: where

text: the

text: estimated

text: value

text: of

text: (µ,

text: σ,

text: s)

text: equals

text: to

text: The

text: ﬁtting

text: statistics

text: we

text: consider

text: here

text: is

text: the

text: Pearson’s

text: Chi-square,

text: the

text: Chi-square

text: statis-

text: ζYT

text: and

text: exp

text: ζT

text: are

text: given

text: as

text: in

text: which

text: are

text: just

text: a

text: re-scale

text: of

text: charge

text: and

text: LOS

text: with

text: the

text: scale

text: deter-

text: mined

text: by

text: the

text: value

text: of

text: explanatory

text: vairables

text: through

text: regression

text: equation

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: p (y, t) Prob {Y ∈ (y − δ, y)} (cid:0) (cid:1)  = lim t ´ δ→0  δ   g˜g˜((yy−,tδ,,tt),t) p (y0, 0) · q˜1 g˜−1 (y0, 0, t) , t dy0   δ  ´  = li→m + δ 0 · − − − y p (y , 0) (q˜ (y δ, S (y , y δ)) q˜ (y, S (y , y))) dy g˜(y,t,t) 0 1 0 1 0 0 δ (A.4) It is not hard to show:(cid:0) (cid:1) ´ · − g˜g˜((yy−,tδ,,tt),t) p (y0, 0) q˜1 g˜ 1 (y0, 0, t) , t dy0 · ·∂g˜(y, t, t) lim = p (g˜(y, t, t) , 0) q˜ (y, t) δ→0 δ 1 ∂y (A.5) and ´ · − − − y p (y ,(cid:18)0) (q˜ (y δ, S (y , y δ)) q˜ (y, S (y , y))) dy (cid:19) ˆlim g˜(y,t,t) 0 1 0 1 0 0 → δ 0 δ y · −∂q˜ (y, S (y , y)) − ∂q˜ (y, S (y , y)) · ∂S (y , y) = p (y , 0) 1 0 1 0 0 dy 0 ∂y ∂t ∂y 0 g˜(y,t,t) (A.6) (cid:48) Through analyzing the solution trajectory of the ODE y = q˜(y, t), it is easy to verify ∂S (y , y) 1 0 = ∂y q˜(y, S (y , y)) 0 S (g˜(y, t, t) , y) = t and − ∂g˜(y, s, s) 1 · ∂g˜(y, s, s) = ∂y q˜(y, s) ∂s Consequently, we have 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: p

label: equation

text: (y,

text: t)

text: Prob

text: {Y

text: (y

text: δ,

text: y)}

text: lim

text: t

text: δ→0

text: δ

text: g˜g˜((yy−,tδ,,tt),t)

text: p

text: g˜−1

text: t)

text: t

text: δ

text: li→m

text: δ

text: y

text: p

text: (y

text: (q˜

text: (y

text: δ,

text: S

text: (y

text: y

text: δ))

text: q˜

text: (y,

text: S

text: (y

text: y)))

text: dy

text: g˜(y,t,t)

text: δ

text: It

label: paragraph

text: is

text: not

text: hard

text: to

text: g˜g˜((yy−,tδ,,tt),t)

text: p

text: g˜

text: t)

text: t

text: ·∂g˜(y,

text: t,

text: t)

text: lim

text: p

text: (g˜(y,

text: t,

text: t)

text: q˜

text: (y,

text: t)

text: δ→0

text: δ

text: ∂y

text: and

text: y

text: p

text: (y

text: (q˜

text: (y

text: δ,

text: S

text: (y

text: y

text: δ))

text: q˜

text: (y,

text: S

text: (y

text: y)))

text: dy

text: ˆlim

text: g˜(y,t,t)

text: δ

text: δ

text: y

text: −∂q˜

text: (y,

text: S

text: (y

text: y))

text: ∂q˜

text: (y,

text: S

text: (y

text: y))

text: ∂S

text: (y

text: y)

text: p

text: (y

text: dy

text: ∂y

text: ∂t

text: ∂y

text: g˜(y,t,t)

text: Through

text: analyzing

text: the

text: solution

text: trajectory

text: of

text: the

text: ODE

text: y

text: q˜(y,

text: t),

text: it

text: is

text: easy

text: to

text: verify

text: ∂S

text: (y

text: y)

text: ∂y

text: q˜(y,

text: S

text: (y

text: y))

text: S

text: (g˜(y,

text: t,

text: t)

text: y)

text: t

text: and

text: ∂g˜(y,

text: s,

text: s)

text: ∂g˜(y,

text: s,

text: s)

text: ∂y

text: q˜(y,

text: s)

text: ∂s

text: Consequently,

text: we

text: have

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:92) (cid:91) { ∈ − ≥ } { ∈ − ≥ } X (y δ,y),T t = G (y δ,y),T t t t { ∈ − ≤ } (cid:92) = (cid:91) G (y δ,y),s T < s { · · ≤ · } si i i+1 ∆>0 si=i ∆:i=0,...,n,n ∆ t<(n+1) ∆ { ∈ − ≤ } − { ∈ − ≤ } = ( G (y δ,y),s T G (y δ,y),s T ) { · · ≤ · } si i si i+1 ∆>0 si=i ∆:i=0,...,n,n ∆ t<(n+1) ∆ (A.9) , therefore (cid:88) (cid:16) (cid:16) (cid:17) (cid:16) (cid:17)(cid:17) nt,∆ · − · Ay,t,δ =∆li→m0 (cid:88) (cid:16)E (cid:16)1{Gsi∈(y−δ,y)} 1{si≤T} E (cid:17)1{Gsi∈(cid:16)(y−δ,y)} 1{si+∆≤T} (cid:17)(cid:17) i=0 nt,∆ · ≤ | − · ≤ | =∆li→m0 E 1{Gsi∈(y−δ,y)} E (si T Gsi) E 1{Gsi∈(y−δ,y)} E (si + ∆ T Gsi) i=0 (A.10) Notice that ˆ ∞ ≤ | (cid:32) ≤ | | (cid:33) (cid:32) (cid:33) E (s + ∆ T Gs = x) = ˆ E (s + ∆ T Gs+∆,Gs = xˆ)dP (Gs+∆ Gs = x) ˆ 0 ∞ ≤ | s+∆ s+∆ | = E s + ∆ T G = x + (cid:15) dτ,G = x dP (cid:15) dτ G = x s+∆ τ s τ s 0 s s ´ (A.11) → s+∆ In addition, using the right-continuity of decision process I (., X , t), (cid:15) dτ → t s τ 0 a.s as ∆ 0 and the continuity of q˜ , we have: 1 ≤ | lim E (s + ∆ T G = x) = q˜ (x, s) (A.12) → s 1 ∆ 0 and (cid:16) (cid:16) (cid:17) (cid:16) (cid:17)(cid:17) ´ ´ ´ ≤ | − ∞ ≤ | | lim → E (s + ∆ T G = x) E s + ∆ T G = x + s+∆ (cid:15) dτ dP s+∆ (cid:15) dτ G = x = 0, ∆ 0 s 0 s+∆ s τ s τ s (A.13) (cid:16) (cid:17) |´ where dP (dG G = x) is the conditional probability inuced by G s+∆ s s+∆ ´ s+∆ | given G = x and dP (cid:15) dτ G = x is the conditional probability induced s s τ s s+∆ by the increment (cid:15) dτ given G = x. Plug A.12, A.13 and A.11 into A.10, s τ s we have the following 21

text: X

text: (y

text: δ,y),T

text: t

text: G

text: (y

text: δ,y),T

text: t

text: t

text: t

text: G

text: (y

text: δ,y),s

text: T

text: s

text: si

text: i

text: si=i

text: G

text: (y

text: δ,y),s

text: T

text: G

text: (y

text: δ,y),s

text: T

text: si

text: i

text: si

text: si=i

text: therefore

text: nt,∆

text: Ay,t,δ

text: E

text: nt,∆

text: E

text: E

text: (si

text: T

text: Gsi)

text: E

text: E

text: (si

text: T

text: Gsi)

text: Notice

text: that

text: ˆ

text: E

text: (s

text: T

text: Gs

text: x)

text: ˆ

text: E

text: (s

text: T

text: Gs+∆,Gs

text: xˆ)dP

text: (Gs+∆

text: Gs

text: x)

text: ˆ

text: s+∆

text: s+∆

text: E

text: s

text: T

text: G

text: x

text: dτ,G

text: x

text: dP

text: dτ

text: G

text: x

text: s+∆

text: τ

text: s

text: τ

text: s

text: s

text: s

text: s+∆

text: In

text: addition,

text: using

text: the

text: right-continuity

text: of

text: decision

text: process

text: I

text: X

text: t),

text: dτ

text: t

text: s

text: τ

text: a.s

text: as

text: and

text: the

text: continuity

text: of

text: q˜

text: we

text: have:

text: lim

text: E

text: (s

text: T

text: G

text: x)

text: q˜

text: (x,

text: s)

text: s

text: and

text: lim

text: E

text: (s

text: T

text: G

text: x)

text: E

text: s

text: T

text: G

text: x

text: s+∆

text: dτ

text: dP

text: s+∆

text: dτ

text: G

text: x

text: s

text: s+∆

text: s

text: τ

text: s

text: τ

text: s

text: where

text: dP

text: (dG

text: G

text: x)

text: is

text: the

text: conditional

text: probability

text: inuced

text: by

text: G

text: s+∆

text: s

text: s+∆

text: s+∆

text: given

text: G

text: x

text: and

text: dP

text: dτ

text: G

text: x

text: is

text: the

text: conditional

text: probability

text: induced

text: s

text: s

text: τ

text: s

text: s+∆

text: by

text: the

text: increment

text: dτ

text: given

text: G

text: x.

text: Plug

text: and

text: into

text: s

text: τ

text: s

text: we

text: have

text: the

text: following


text:  (cid:16) (cid:17) (cid:88)  ˆ − − p (t) − 2 · N θ · e · e(Sn−a)·t · 1 · (cid:18) exp(cid:18) √(ln(y2)σnµn)2(cid:19)(cid:19)dy ·(cid:33)a T πγ n=1 n 1,dn dˆn [0,∞) 2πσn − − · − · · · · − ln (y) µ e e(Sn a) t S 1 1 Φ n dy 1,dn n dn ∞ σ [0, ) n − · − · 2 exp( a t)× (cid:16) (cid:17) (cid:16) (cid:17) = (cid:88) πγ N θ · e · eSn·t · 1 · ˆ (cid:18) y(cid:16)·expγ(−a·t) 2(cid:17) (cid:19) · exp −√(ln(y2)σ−nµn)2 dy · a n=1 n 1,dn dn [0,∞) (cid:16) 1 + y·exp(cid:17)(−a·t) 2(cid:18) (cid:18) 2πσn (cid:19)(cid:19)  γ  ˆ (cid:18) y(cid:16)·exp(−a·t) 2(cid:17) (cid:19) −  − e · eSn·t · S · 1 · γ · 1 − Φ ln (y) µn dy 1,dn n dn ∞ · − · 2 σ [0, ) 1 + y exp( a t) n γ (C.3) (cid:0) (cid:0) (cid:0) (cid:1)(cid:1)(cid:1) · − · Obviously, the right hand side of Equation C.3 is bounded by C exp ( a t) · · where the constant C can be chosen to be a number no less than 2 max (E ) · · · · πγ n n a + maxn maxt e1,dn eSn t Sn 1dn where En is the expectation of log- normal distribution speciﬁed by (µ , σ ). The second term in the left hand side n n C.3 can be expresse(cid:88)d as (cid:16) (cid:17) 2 · N · · · − · · − · θ E e e(Sn a) t (a S ) 1 (C.4) πγ n n 1,d´n ´ n dn n=1 ∞ · ∞ − where we use the relation that f (y) ydy = (1 F (y)) dy with f 0 ∞ 0 being a probability density function over [0, ) and F is its cumulative distri- bution function. Since · − · · − · e e(Sn a) t (a S ) 1 1,dn n dn is the density function of a Coxian Phase Type distribution associated with − transition matrix S a, expression C.4 is just a linear combination of Coxian n Phase Type distributions with all coeﬃcients positive. Consequently, the result- ing function is a density function of another Coxian Phase Type distribution ⊕ with transition matrix S = N S . n=1 n In sum, we obtain the desired decomposition for the marginal LOS density as a Coxian Phase Type density (generalized4) and a residual term controlled · − · by C exp ( a t). For charge density p , to show it has the right tail asymptotically equivalent YT to the right tail of some log-normal density function, it suﬃces to show (cid:80) 4 Notice that for this new Coxian Phase Type distribution, it may not be a probability distribution because its total mass (=π2γ Nn=1 θnEn) may not be 1. But it is always finite and positive, therefore it is different from a probability measure only by multiplying a scalar. For the purpose of approximating the shape of density function, this result is good enough. 25 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ˆ

text: p

text: (t)

text: N

text: θ

text: e

text: e(Sn−a)·t

text: T

text: πγ

text: n

text: dˆn

text: 2πσn

text: ln

text: (y)

text: µ

text: e

text: e(Sn

text: a)

text: t

text: S

text: Φ

text: n

text: dy

text: n

text: dn

text: σ

text: n

text: exp(

text: a

text: t)×

text: πγ

text: N

text: θ

text: e

text: eSn·t

text: ˆ

text: exp

text: dy

text: a

text: n

text: dn

text: 2πσn

text: γ

text: ˆ

text: e

text: eSn·t

text: S

text: γ

text: Φ

text: ln

text: (y)

text: µn

text: dy

text: n

text: dn

text: σ

text: y

text: exp(

text: a

text: t)

text: n

text: γ

text: Obviously,

text: the

text: right

text: hand

text: side

text: of

text: Equation

text: is

text: bounded

text: by

text: C

text: exp

text: a

text: t)

text: where

text: the

text: constant

text: C

text: can

text: be

text: chosen

text: to

text: be

text: a

text: number

text: no

text: less

text: than

text: max

text: (E

text: πγ

text: n

text: n

text: a

text: maxn

text: maxt

text: eSn

text: t

text: Sn

text: where

text: En

text: is

text: the

text: expectation

text: of

text: log-

text: normal

text: distribution

text: speciﬁed

text: by

text: (µ

text: σ

text: The

text: second

text: term

text: in

text: the

text: left

text: hand

text: side

text: n

text: n

text: can

text: be

text: as

text: N

text: θ

text: E

text: e

text: e(Sn

text: a)

text: t

text: (a

text: S

text: πγ

text: n

text: n

text: n

text: dn

text: where

text: we

text: use

text: the

text: relation

text: that

text: f

text: (y)

text: ydy

text: F

text: (y))

text: dy

text: with

text: f

text: being

text: a

text: probability

text: density

text: function

text: over

text: and

text: F

text: is

text: its

text: cumulative

text: distri-

text: bution

text: function.

text: Since

text: e

text: e(Sn

text: a)

text: t

text: (a

text: S

text: n

text: dn

text: is

text: the

text: density

text: function

text: of

text: a

text: Coxian

text: Phase

text: Type

text: distribution

text: associated

text: with

text: transition

text: matrix

text: S

text: a,

text: expression

text: is

text: just

text: a

text: linear

text: combination

text: of

text: Coxian

text: n

text: Phase

text: Type

text: distributions

text: with

text: all

text: coeﬃcients

text: positive.

text: Consequently,

text: the

text: result-

text: ing

text: function

text: is

text: a

text: density

text: function

text: of

text: another

text: Coxian

text: Phase

text: Type

text: distribution

text: with

text: transition

text: matrix

text: S

text: N

text: S

text: n

text: In

text: sum,

text: we

text: obtain

text: the

text: desired

text: decomposition

text: for

text: the

text: marginal

text: LOS

text: density

text: as

text: a

text: Coxian

text: Phase

text: Type

text: density

text: and

text: a

text: residual

text: term

text: controlled

text: by

text: C

text: exp

text: a

text: t).

text: For

text: charge

text: density

text: p

text: to

text: show

text: it

text: has

text: the

text: right

text: tail

text: asymptotically

text: equivalent

text: YT

text: to

text: the

text: right

text: tail

text: of

text: some

text: log-normal

text: density

text: function,

text: it

text: suﬃces

text: to

text: show

text: Notice

text: that

text: for

text: this

text: new

text: Coxian

text: Phase

text: Type

text: distribution,

text: it

text: may

text: not

text: be

text: a

text: probability

text: distribution

text: because

text: its

text: total

text: mass

text: θnEn)

text: may

text: not

text: be

text: But

text: it

text: is

text: always

text: finite

text: and

text: positive,

text: therefore

text: it

text: is

text: different

text: from

text: a

text: probability

text: measure

text: only

text: by

text: multiplying

text: a

text: scalar.

text: For

text: the

text: purpose

text: of

text: approximating

text: the

text: shape

text: of

text: density

text: function,

text: this

text: result

text: is

text: good

text: enough.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [9] Peacock, J. (1983). Two-dimensional goodness-of-ﬁt testing in astronomy. Monthly Notices of the Royal Astronomical Society. 202 (1983), no. 3, 615– 627. [10] Fasano, Giovanni and Franceschini, Alberto (1987), A multidimen- sional version of the Kolmogorov–Smirnov test. Monthly Notices of the Royal Astronomical Society. 225, no. 1, 155–170. [11] Amemiya, T. (1985). Advanced Econometrics. Harvard University Press, Cambridge. [12] Evans, L. (2010). Partial diﬀerential equations 2. American Mathematical Society. [13] Schwarz, Gideon and others (1978), Estimating the dimension of a model. The annals of statistics. 6, no. 2, 461–464. [14] Marshall, Adele H and McClean, Sally I and Shapcott, CM and Millard, Peter H (2002), Modelling patient duration of stay to fa- cilitate resource management of geriatric hospitals. Health Care Management Science. 5, no. 4, 313–319. [15] Marshall, Adele H and Shaw, Barry and McClean, Sally I (2007), Estimating the costs for a group of geriatric patients using the Cox- ian phase-type distribution. Statistics in medicine. 26, no. 13, 2716–2729. [16] Marshall, Adele and Vasilakis, Christos and El-Darzi, Elia (2005), Length of stay-based patient ﬂow models: recent developments and future directions. Health Care Management Science. 8, no. 3, 213–220. [17] Green, Peter J (199 5), Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika. 82, no. 4, 711– 732. 30

label: reference

text: Peacock,

text: J.

text: Two-dimensional

text: goodness-of-ﬁt

text: testing

text: in

text: astronomy.

text: Monthly

text: Notices

text: of

text: the

text: Royal

text: Astronomical

text: Society.

text: no.

text: Fasano,

text: Giovanni

text: and

text: Franceschini,

text: Alberto

text: A

text: multidimen-

text: sional

text: version

text: of

text: the

text: Kolmogorov–Smirnov

text: test.

text: Monthly

text: Notices

text: of

text: the

text: Royal

text: Astronomical

text: Society.

text: no.

text: Amemiya,

text: T.

text: Advanced

text: Econometrics.

text: Harvard

text: University

text: Press,

text: Cambridge.

text: Evans,

text: L.

text: Partial

text: diﬀerential

text: equations

text: American

text: Mathematical

text: Society.

text: Schwarz,

text: Gideon

text: and

text: others

text: Estimating

text: the

text: dimension

text: of

text: a

text: model.

text: The

text: annals

text: of

text: statistics.

text: no.

text: Marshall,

text: Adele

text: H

text: and

text: McClean,

text: Sally

text: I

text: and

text: Shapcott,

text: CM

text: and

text: Millard,

text: Peter

text: H

text: Modelling

text: patient

text: duration

text: of

text: stay

text: to

text: fa-

text: cilitate

text: resource

text: management

text: of

text: geriatric

text: hospitals.

text: Health

text: Care

text: Management

text: Science.

text: no.

text: Marshall,

text: Adele

text: H

text: and

text: Shaw,

text: Barry

text: and

text: McClean,

text: Sally

text: I

text: Estimating

text: the

text: costs

text: for

text: a

text: group

text: of

text: geriatric

text: patients

text: using

text: the

text: Cox-

text: ian

text: phase-type

text: distribution.

text: Statistics

text: in

text: medicine.

text: no.

text: Marshall,

text: Adele

text: and

text: Vasilakis,

text: Christos

text: and

text: El-Darzi,

text: Elia

text: Length

text: of

text: stay-based

text: patient

text: ﬂow

text: models:

text: recent

text: developments

text: and

text: future

text: directions.

text: Health

text: Care

text: Management

text: Science.

text: no.

text: Green,

text: Peter

text: J

text: Reversible

text: jump

text: Markov

text: chain

text: Monte

text: Carlo

text: computation

text: and

text: Bayesian

text: model

text: determination.

text: Biometrika.

text: no.


text: (cid:18) (cid:16) (cid:17) (cid:19) 2 p (cid:48) (y, 0) = x,x 2 · · − − · 1 + y · π exp ( β β x) exp(β0,c+βc x) 0,c c (cid:18) y (cid:19) q˜x,x(cid:48) (y, t) = exp (β + β · x(cid:48)) 0,los los y t q˜1,x,x(cid:48) (y, t) = q˜1 exp (β + β · x), exp (β + β · x(cid:48)) 0,y y 0,los los where q˜ is given as in Equation 3.3. 1 Proof for Proposition 3.5 is in Appendix . Proposition 3.5 shows that the correspondence between the parameter space and the parametric family of func- tions q˜, q˜ and p(., 0) is one-to-one, which veriﬁes the part 2 of Principle 3.3. 1 3.1.3 Expression for Log-Likelihood Function Combining the regression equation 2.11, the joint density function given in 3.4 and the log-likelihood function in 3.1, we obtain the parametric form of the log-likelihood function as below:     (cid:88)    (cid:32) (cid:18) (cid:19) (cid:33)  K 2 · exp(−β − β · x(cid:48) ) · exp(−β − β · x ) L := ln 0,los los k 0,c c k + k=1 π 1+ yk·exp(−tk/exp(β0,lo·s+βlos·x(cid:48)k)) 2 (cid:16) (cid:17)   (cid:88)  exp(β0,c+βc xk)  (cid:88)K ln nN=1θn · e1,dn · eexp(β0,(lSons+−β1)los·x(cid:48)k)(cid:18)·tk · 1dn(cid:18)· exp −(ln(yk√)−2βπ0σ,2cσn−nβc·xk−µn)(cid:19)2 (cid:19)−(cid:33) k=1 e1,dn · eexp(β0,(lSons+−β1)los·x(cid:48)k)·tk · Sn · 1dn · 1 − Φ ln(yk) − β0,cσ− βc · xk − µn n (3.5) and the following constrained maximization problem that we have to solve in order to get the estimated parameters: (cid:88) maxL (θ; β; LN; s) K s.t. θ = 1 k (3.6) k=1 ≥ θ 0 k = 1, . . . K k ≥ σ 0 k = 1, . . . , K k (cid:0) (cid:1) where the four families of parameters to be solved are the weight vector θ = (θ1, . . . , θK), the regression coeﬃcients β = β0,c,...,β|x|,c,β0,los,...,β|x(cid:48)|,los and parameter vectors for the log-normal components LN = (µ1,...,µK,σ1,...,σK), and the parameter vectors for the Phase Type components s = (s , . . . , s ) where − 1 K each s is a 2d 1 dimensional vector which determines the transition matrix k k S in the following way: k 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: p

text: (y,

text: x,x

text: y

text: π

text: exp

text: β

text: β

text: x)

text: x)

text: c

text: y

text: (y,

text: t)

text: exp

text: (β

text: β

text: los

text: y

text: t

text: (y,

text: t)

text: exp

text: (β

text: β

text: x),

text: exp

text: (β

text: β

text: y

text: los

text: where

text: q˜

text: is

text: given

text: as

text: in

text: Equation

text: Proof

text: for

text: Proposition

text: is

text: in

text: Appendix

text: Proposition

text: shows

text: that

text: the

text: correspondence

text: between

text: the

text: parameter

text: space

text: and

text: the

text: parametric

text: family

text: of

text: func-

text: tions

text: q˜,

text: q˜

text: and

text: p(.,

text: is

text: one-to-one,

text: which

text: veriﬁes

text: the

text: part

text: of

text: Principle

text: Expression

text: for

text: Log-Likelihood

text: Function

text: Combining

text: the

text: regression

text: equation

text: the

text: joint

text: density

text: function

text: given

text: in

text: and

text: the

text: log-likelihood

text: function

text: in

text: we

text: obtain

text: the

text: parametric

text: form

text: of

text: the

text: log-likelihood

text: function

text: as

text: below:

text: K

text: 2

text: exp(−β

text: β

text: exp(−β

text: β

text: x

text: L

text: ln

text: los

text: k

text: c

text: k

text: π

text: xk)

text: ln

text: exp

text: Sn

text: Φ

text: ln(yk)

text: β0,cσ−

text: βc

text: xk

text: µn

text: n

text: and

text: the

text: following

text: constrained

text: maximization

text: problem

text: that

text: we

text: have

text: to

text: solve

text: in

text: order

text: to

text: get

text: the

text: estimated

text: parameters:

text: maxL

text: (θ;

text: β;

text: LN;

text: s)

text: K

text: s.t.

text: θ

text: k

text: θ

text: k

text: K

text: k

text: σ

text: k

text: K

text: k

text: where

text: the

text: four

text: families

text: of

text: parameters

text: to

text: be

text: solved

text: are

text: the

text: weight

text: vector

text: θ

text: θK),

text: the

text: regression

text: coeﬃcients

text: β

text: and

text: parameter

text: vectors

text: for

text: the

text: log-normal

text: components

text: LN

text: and

text: the

text: parameter

text: vectors

text: for

text: the

text: Phase

text: Type

text: components

text: s

text: (s

text: s

text: where

text: K

text: each

text: s

text: is

text: a

text: dimensional

text: vector

text: which

text: determines

text: the

text: transition

text: matrix

text: k

text: k

text: S

text: in

text: the

text: following

text: way:

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: inﬁnitely often. Subsequently, Impagliazzo and Wigderson [9] gave a “high- end” derandomization of BPP. They proved that, if E does not have 2(cid:15)n size Boolean circuits, then BPP = P. We now know that, in certain settings, circuit lower bounds and derandomization are equivalent. Impagliazzo et al, showed that any non-trivial derandomization of the class MA implies that NEXP does not have polynomial size deterministic circuits [8]. Kabanets and Impagliazzo subsequently proved that derandomizing the well known Polynomial Identity Testing problem is equivalent to circuit lower bounds [11]. Aydinlio˘glu and van Melkebeek [1] have recently introduced augmented Arthur-Merlin protocols to extend the equivalence of circuit lower bounds and derandomization to non-deterministic circuits. Using augmented AM, Aydinlio˘glu and van Melkebeek showed that derandomizing promise AM in Σ SubEXP with n(cid:15) bits of advice is equivalent to polynomial size non- 2 deterministic circuit lower bounds for Σ E. 2 In this paper, we investigate non-deterministic circuit lower bounds of uniform classes. We prove that non-deterministic circuit lower bounds trans- late downward for Sigma -time classes. Speciﬁcally, we show that if Σ E 2 2 does not have polynomial size non-deterministic circuits, then Σ SubEXP 2 does not have ﬁxed polynomial size non-deterministic circuits. To prove this result, we give ﬁxed polynomial size non-deterministic lower bounds for augmented Arthur-Merlin protocols, which may be of independent interest. To achieve this, we use a technique developed by Santhanam [16] to prove analogous results for MA. While circuit lower bounds are notoriously hard to prove, there has been ∩ important progress in this direction. Kannan proved that Σ P Π P does not 2 2 have ﬁxed polynomial size deterministic circuits [12]. Subsequently, Kobler and Watanabe improved this lower bound holds for the weaker class ZPPNP [14]. Cai was able to strengthen this further by showing that S P does 2 not have ﬁxed polynomial size deterministic circuits [4]. Vinodchandran proved ﬁxed nk circuit lower bounds for the class PP. Santhanam, using tools from interactive proof protocols [15], [18] and program checking [3], proved that MA with one bit of advice does not have ﬁxed polynomial size deterministic circuits. There have been fewer unconditional lower bounds for non-deterministic circuits. The smallest class known to have ﬁxed poly- nomial size non-deterministic circuits is S PNP, which follows by relativizing 2 Cai’s result [4]. In this paper, we show that Santhanam’s technique can be applied to the augmented Arthur-Merlin protocols of [1]. This improves the smallest class known to have ﬁxed size non-deterministic circuits. One of the principal interests in proving non-deterministic circuit lower bounds is the derandomization of AM. The work of Klivans and van Melke- beek [13]; Shaltiel and Umans [17] shows that derandomization of prAM follows from non-deterministic circuit lower bounds. Recently, progress has been made on achieving non-trivial derandomization of AM in Σ -time 2 2

text: inﬁnitely

text: often.

text: Subsequently,

text: Impagliazzo

text: and

text: Wigderson

text: gave

text: a

text: “high-

text: end”

text: derandomization

text: of

text: BPP.

text: They

text: proved

text: that,

text: if

text: E

text: does

text: not

text: have

text: size

text: Boolean

text: circuits,

text: then

text: BPP

text: P.

text: We

text: now

text: know

text: that,

text: in

text: certain

text: settings,

text: circuit

text: lower

text: bounds

text: and

text: derandomization

text: are

text: equivalent.

text: Impagliazzo

text: et

text: al,

text: showed

text: that

text: any

text: non-trivial

text: derandomization

text: of

text: the

text: class

text: MA

text: implies

text: that

text: NEXP

text: does

text: not

text: have

text: polynomial

text: size

text: deterministic

text: circuits

text: Kabanets

text: and

text: Impagliazzo

text: subsequently

text: proved

text: that

text: derandomizing

text: the

text: well

text: known

text: Polynomial

text: Identity

text: Testing

text: problem

text: is

text: equivalent

text: to

text: circuit

text: lower

text: bounds

text: Aydinlio˘glu

text: and

text: van

text: Melkebeek

text: have

text: recently

text: introduced

text: augmented

text: Arthur-Merlin

text: protocols

text: to

text: extend

text: the

text: equivalence

text: of

text: circuit

text: lower

text: bounds

text: and

text: derandomization

text: to

text: non-deterministic

text: circuits.

text: Using

text: augmented

text: AM,

text: Aydinlio˘glu

text: and

text: van

text: Melkebeek

text: showed

text: that

text: derandomizing

text: promise

text: AM

text: in

text: Σ

text: SubEXP

text: with

text: bits

text: of

text: advice

text: is

text: equivalent

text: to

text: polynomial

text: size

text: non-

text: deterministic

text: circuit

text: lower

text: bounds

text: for

text: Σ

text: E.

text: In

text: this

text: paper,

text: we

text: investigate

text: non-deterministic

text: circuit

text: lower

text: bounds

text: of

text: uniform

text: classes.

text: We

text: prove

text: that

text: non-deterministic

text: circuit

text: lower

text: bounds

text: trans-

text: late

text: downward

text: for

text: Sigma

text: -time

text: classes.

text: Speciﬁcally,

text: we

text: show

text: that

text: if

text: Σ

text: E

text: does

text: not

text: have

text: polynomial

text: size

text: non-deterministic

text: circuits,

text: then

text: Σ

text: SubEXP

text: does

text: not

text: have

text: ﬁxed

text: polynomial

text: size

text: non-deterministic

text: circuits.

text: To

text: prove

text: this

text: result,

text: we

text: give

text: ﬁxed

text: polynomial

text: size

text: non-deterministic

text: lower

text: bounds

text: for

text: augmented

text: Arthur-Merlin

text: protocols,

text: which

text: may

text: be

text: of

text: independent

text: interest.

text: To

text: achieve

text: this,

text: we

text: use

text: a

text: technique

text: developed

text: by

text: Santhanam

text: to

text: prove

text: analogous

text: results

text: for

text: MA.

text: While

text: circuit

text: lower

text: bounds

text: are

text: notoriously

text: hard

text: to

text: prove,

text: there

text: has

text: been

text: important

text: progress

text: in

text: this

text: direction.

text: Kannan

text: proved

text: that

text: Σ

text: P

text: Π

text: P

text: does

text: not

text: have

text: ﬁxed

text: polynomial

text: size

text: deterministic

text: circuits

text: Subsequently,

text: Kobler

text: and

text: Watanabe

text: improved

text: this

text: lower

text: bound

text: holds

text: for

text: the

text: weaker

text: class

text: ZPPNP

text: Cai

text: was

text: able

text: to

text: strengthen

text: this

text: further

text: by

text: showing

text: that

text: S

text: P

text: does

text: not

text: have

text: ﬁxed

text: polynomial

text: size

text: deterministic

text: circuits

text: Vinodchandran

text: proved

text: ﬁxed

text: nk

text: circuit

text: lower

text: bounds

text: for

text: the

text: class

text: PP.

text: Santhanam,

text: using

text: tools

text: from

text: interactive

text: proof

text: protocols

text: and

text: program

text: checking

text: proved

text: that

text: MA

text: with

text: one

text: bit

text: of

text: advice

text: does

text: not

text: have

text: ﬁxed

text: polynomial

text: size

text: deterministic

text: circuits.

text: There

text: have

text: been

text: fewer

text: unconditional

text: lower

text: bounds

text: for

text: non-deterministic

text: circuits.

text: The

text: smallest

text: class

text: known

text: to

text: have

text: ﬁxed

text: poly-

text: nomial

text: size

text: non-deterministic

text: circuits

text: is

text: S

text: PNP,

text: which

text: follows

text: by

text: relativizing

text: Cai’s

text: result

text: In

text: this

text: paper,

text: we

text: show

text: that

text: Santhanam’s

text: technique

text: can

text: be

text: applied

text: to

text: the

text: augmented

text: Arthur-Merlin

text: protocols

text: of

text: This

text: improves

text: the

text: smallest

text: class

text: known

text: to

text: have

text: ﬁxed

text: size

text: non-deterministic

text: circuits.

text: One

text: of

text: the

text: principal

text: interests

text: in

text: proving

text: non-deterministic

text: circuit

text: lower

text: bounds

text: is

text: the

text: derandomization

text: of

text: AM.

text: The

text: work

text: of

text: Klivans

text: and

text: van

text: Melke-

text: beek

text: Shaltiel

text: and

text: Umans

text: shows

text: that

text: derandomization

text: of

text: prAM

text: follows

text: from

text: non-deterministic

text: circuit

text: lower

text: bounds.

text: Recently,

text: progress

text: has

text: been

text: made

text: on

text: achieving

text: non-trivial

text: derandomization

text: of

text: AM

text: in

text: Σ

text: -time


text: In a similar manner, and with the same assumption on the behavior of (cid:48) (cid:48) (cid:48) (cid:48) M , deﬁne the promise problem ΓM = (ΓM , ΓM ) by Y N (cid:48) {(cid:104) (cid:105) | (cid:48) ≥ } ΓM = x, C C is a PSV circuit s.t. Pr[M L(C))(x) = 1] 2/3 Y (cid:48) {(cid:104) (cid:105) | (cid:48) ≥ } ΓM = x, C C is a PSV circuit s.t. Pr[M L(C)(x) = 0] 2/3 . N (cid:48) Lemma 2. Let L, M and M be as in the deﬁnition of Lemma 1. Let ΓM (cid:48) (cid:48) and ΓM be the promise problems deﬁned above. Then ΓM and ΓM are in prAM. (cid:48) Proof. We give the Arthur-Merlin protocol for ΓM. The protocol for ΓM (cid:104) (cid:105) is identical. On input x, C , the Arthur-Merlin protocol works as follows. Arthur guesses a random string r, and sends r to Merlin. Merlin responds with a sequence of witnesses w , . . . , w . Arthur then simulates M with 1 p(n) L(C) as its oracle by using the provided witnesses. That is, for every query q , Arthur simulates C(q , w ). If for any j, C(q , w ) does not have a 1 at j j j j j its ﬂag gate, Arthur immediately halts and rejects. Otherwise, Arthur uses the value of C(q , w ) as the oracle response and continues. j j (cid:48) (cid:48) From the deﬁnition of M and M , it is clear that ΓM and ΓM are in prAM. The usefulness of the coNP veriﬁer in the deﬁnition of augmented AM protocols is that it allows for us to simulate interactive proof protocols. In ⊆ the deterministic circuit setting, we are able to prove that PSPACE P/poly implies that PSPACE = MA. This follows from the fact that Merlin can send Arthur a Boolean circuit claiming to compute the provers strategy, and Arthur simply simulates the interactive proof protocol using this cir- cuit as the oracle. In the non-deterministic setting, however, this method breaks down. The essential diﬃculty is that Arthur cannot know if the non- deterministic circuit returns “no” on every path, or just the one Merlin gives. The inclusion of a coNP veriﬁer allows the proof for deterministic circuits to extend to the non-deterministic setting. Using this strategy, Aydinlio˘glu and van Melkebeek [1] proved the following Lemma. ⊆ ⊆ Theorem 2. If PSPACE NP/poly, then PSPACE AugAM. For the sake of clarity, we will break the proof of our main theorem into two parts. The ﬁrst part uses Santhanam’s technique [16] to show that augmented Arthur-Merlin protocols with one bit of advice do not have ﬁxed polynomial size SV-circuits. We then modify this proof slightly to achieve ∩ the stronger statement, that class (AugAM coAugAM)/1 does not have ﬁxed size non-deterministic circuits. ∈ N ∈ Theorem 3. For every k there is a language A AugAM/1 such that ∈ L / SVSIZE(nk). 6 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: In

text: a

text: similar

text: manner,

text: and

text: with

text: the

text: same

text: assumption

text: on

text: the

text: behavior

text: of

text: M

text: deﬁne

text: the

text: promise

text: problem

text: ΓM

text: (ΓM

text: ΓM

text: by

text: Y

text: N

text: ΓM

text: x,

text: C

text: C

text: is

text: a

text: PSV

text: circuit

text: s.t.

text: Pr[M

text: L(C))(x)

text: Y

text: ΓM

text: x,

text: C

text: C

text: is

text: a

text: PSV

text: circuit

text: s.t.

text: Pr[M

text: L(C)(x)

text: N

text: Lemma

text: Let

text: L,

text: M

text: and

text: M

text: be

text: as

text: in

text: the

text: deﬁnition

text: of

text: Lemma

text: Let

text: ΓM

text: and

text: ΓM

text: be

text: the

text: promise

text: problems

text: deﬁned

text: above.

text: Then

text: ΓM

text: and

text: ΓM

text: are

text: in

text: prAM.

text: Proof.

text: We

text: give

text: the

text: Arthur-Merlin

text: protocol

text: for

text: ΓM.

text: The

text: protocol

text: for

text: ΓM

text: is

text: identical.

text: On

text: input

text: x,

text: C

text: the

text: Arthur-Merlin

text: protocol

text: works

text: as

text: follows.

text: Arthur

text: guesses

text: a

text: random

text: string

text: r,

text: and

text: sends

text: r

text: to

text: Merlin.

text: Merlin

text: responds

text: with

text: a

text: sequence

text: of

text: witnesses

text: w

text: w

text: Arthur

text: then

text: simulates

text: M

text: with

text: p(n)

text: L(C)

text: as

text: its

text: oracle

text: by

text: using

text: the

text: provided

text: witnesses.

text: That

text: is,

text: for

text: every

text: query

text: q

text: Arthur

text: simulates

text: C(q

text: w

text: If

text: for

text: any

text: j,

text: C(q

text: w

text: does

text: not

text: have

text: a

text: at

text: j

text: j

text: j

text: j

text: j

text: its

text: ﬂag

text: gate,

text: Arthur

text: immediately

text: halts

text: and

text: rejects.

text: Otherwise,

text: Arthur

text: uses

text: the

text: value

text: of

text: C(q

text: w

text: as

text: the

text: oracle

text: response

text: and

text: continues.

text: j

text: j

text: From

text: the

text: deﬁnition

text: of

text: M

text: and

text: M

text: it

text: is

text: clear

text: that

text: ΓM

text: and

text: ΓM

text: are

text: in

text: prAM.

text: The

text: usefulness

text: of

text: the

text: coNP

text: veriﬁer

text: in

text: the

text: deﬁnition

text: of

text: augmented

text: AM

text: protocols

text: is

text: that

text: it

text: allows

text: for

text: us

text: to

text: simulate

text: interactive

text: proof

text: protocols.

text: In

text: the

text: deterministic

text: circuit

text: setting,

text: we

text: are

text: able

text: to

text: prove

text: that

text: PSPACE

text: P/poly

text: implies

text: that

text: PSPACE

text: MA.

text: This

text: follows

text: from

text: the

text: fact

text: that

text: Merlin

text: can

text: send

text: Arthur

text: a

text: Boolean

text: circuit

text: claiming

text: to

text: compute

text: the

text: provers

text: strategy,

text: and

text: Arthur

text: simply

text: simulates

text: the

text: interactive

text: proof

text: protocol

text: using

text: this

text: cir-

text: cuit

text: as

text: the

text: oracle.

text: In

text: the

text: non-deterministic

text: setting,

text: however,

text: this

text: method

text: breaks

text: down.

text: The

text: essential

text: diﬃculty

text: is

text: that

text: Arthur

text: cannot

text: know

text: if

text: the

text: non-

text: deterministic

text: circuit

text: returns

text: “no”

text: on

text: every

text: path,

text: or

text: just

text: the

text: one

text: Merlin

text: gives.

text: The

text: inclusion

text: of

text: a

text: coNP

text: veriﬁer

text: allows

text: the

text: proof

text: for

text: deterministic

text: circuits

text: to

text: extend

text: to

text: the

text: non-deterministic

text: setting.

text: Using

text: this

text: strategy,

text: Aydinlio˘glu

text: and

text: van

text: Melkebeek

text: proved

text: the

text: following

text: Lemma.

text: Theorem

text: If

text: PSPACE

text: NP/poly,

text: then

text: PSPACE

text: AugAM.

text: For

text: the

text: sake

text: of

text: clarity,

text: we

text: will

text: break

text: the

text: proof

text: of

text: our

text: main

text: theorem

text: into

text: two

text: parts.

text: The

text: ﬁrst

text: part

text: uses

text: Santhanam’s

text: technique

text: to

text: show

text: that

text: augmented

text: Arthur-Merlin

text: protocols

text: with

text: one

text: bit

text: of

text: advice

text: do

text: not

text: have

text: ﬁxed

text: polynomial

text: size

text: SV-circuits.

text: We

text: then

text: modify

text: this

text: proof

text: slightly

text: to

text: achieve

text: the

text: stronger

text: statement,

text: that

text: class

text: (AugAM

text: does

text: not

text: have

text: ﬁxed

text: size

text: non-deterministic

text: circuits.

text: N

text: Theorem

text: For

text: every

text: k

text: there

text: is

text: a

text: language

text: A

text: such

text: that

text: L

text: SVSIZE(nk).

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2 Hariharan N. et al. extent by the use of Adaptive Mesh Reﬁnement (AMR) point sources. A ﬁnal example is IFT (Alvarez et al. 2006), schemes (e.g. Kravtsov et al. 1997; Teyssier 2002; Miniati which has been developed to explicitly follow the I-front & Colella 2007; Bryan et al. 2014), which provide a great around a point source. amount of theoretical and algorithmic resources, and have From the above examples, it is clear that AMR-enabled been used extensively to solve a wide range of problems, stand-alone RT codes are increasingly in use and they stand such as numerical relativity, global weather and nuclear fu- to beneﬁt from the advantages that AMR provides. Keep- sion modelling (e.g. Plewa et al. 2003). ing this in mind, we have developed CRASH-AMR, a novel AMR schemes use a mesh or a grid to describe the phys- implementation of the RT code CRASH (Ciardi et al. 2001; ical domain and to progressively increase the grid resolution Maselli et al. 2003; Maselli & Ferrara 2005; Maselli et al. in conﬁned regions of the mesh, based on a set of reﬁnement 2009; Pierleoni et al. 2009; Partl et al. 2011; Graziani et al. criteria. By selectively increasing the resolution only in the 2013), which is interfaced with the open source AMR library interesting part of the domain, AMR methods optimise the CHOMBO (Adams et al. 2011) to perform RT simulations on global memory and computational resource requirements. AMR grids. The aim of this paper is to introduce this new The original idea of AMR was to introduce a ﬁner grid in version, to discuss its implementation details and to show regions of higher numerical error, which can be identiﬁed by the tests that we have done to verify and validate CRASH-AMR. density gradients or by Richardson extrapolation (Berger & The paper is structured as follows. In Section we brieﬂy Oliger 1984; Berger & Colella 1989). However, AMR can introduce AMR and its diﬀerent schemes, the CHOMBO library be employed very ﬂexibly, and diﬀerent reﬁnement criteria is also presented in this context and we mention some of its can be chosen. For example, in cosmological applications it applications. In Section we introduce the ray tracing im- is customary to adopt a Lagrangian criterion in which cells plementation in the CRASH code. In Section we discuss the are reﬁned when their mass is above a given threshold (e.g. method used to couple CRASH and CHOMBO to enable AMR in Wise & Abel 2011). Alternatively, it is also possible to reﬁne CRASH. The tests performed to verify our code are discussed speciﬁc volumes in a Eulerian style, which is advantageous in Section and the results are summarised in Section . The for example if one is interested in resolving turbulent mo- advantages of the code in terms of computational costs is tions inside cosmological halos (e.g. Miniati 2014). highlighted in Appendix and . Here, we discuss the tests AMR is also very ﬂexible from an algorithmic point done to show the dependence on grid-resolution and perfor- of view. For example, it naturally supports divergence- mance of the code. We discuss code performance in terms of free magnetohydrodynamics (e.g. Miniati & Martin 2011; run-time and correctness of results when compared to run- Teyssier et al. 2006; Lee & Deane 2009), it has been used ning RT simulations on uniform grids. to make detailed studies of thermonuclear ﬂashes in FLASH 2 BASICS OF AMR AND THE CHOMBO (Fryxell et al. 2000), and also to simulate the formation of LIBRARY large-scale cosmological structures in ENZO (see e.g. Bryan AMR is a successful technique when a problem presents et al. 2014 and Plewa et al. 2003 for more examples). a highly inhomogeneous spatial distribution implying that Many hydro codes make use of AMR schemes to carry some regions require additional resolution, i.e. additional re- out gas dynamic simulations over a range of spatial scales. ﬁnement. An AMR mesh is deﬁned as structured (SAMR) Some of them are also coupled with RT schemes to per- if its cells (typically cartesian) are connected in a regu- form self-consistent simulations where the RT feedback lar geometry. Un-structured grids composed of triangular is accounted for in the dynamical evolution of the gas. or tetrahedral cells without a regular connectivity can also The Hydrodynamics Adaptive Reﬁnement Tree (HART) code be deﬁned (see for example Mavriplis 1997, Khokhlov 1998, (Gnedin et al. 2009) uses the OTVET approximation for the Springel 2011 and Paardekooper et al. 2008). We limit our 3D RT implementation (Gnedin & Abel 2001), while the cos- discussion to SAMR schemes in this paper. mological hydrodynamics code RAMSES (Rosdahl et al. 2013), There are many alternative ways to reﬁne a certain sub- designed for simulations of structure formation, incorporates domain using diﬀerent SAMR schemes. In the Cell-based RT using the M1 closure formalism (Levermore 1984). Both (CBAMR) scheme each cell of the grid is reﬁned as and when HART and RAMSES make use of the the Fully Threaded Tree required and generally a quad-tree (2D) or and oct-tree (3D) described in Khokhlov (1998) to implement AMR. For the forms the hierarchical structure relating the “coarser” (par- RT ENZO uses an adaptive ray-tracing scheme implemented ent) and “ﬁner” (child) cells (Young et al. 1991). The Block- in the HEALPix library (Abel & Wandelt 2002; Go´rski et al. structured AMR (BSAMR) scheme tags and reﬁnes a region 2005). The interested reader can ﬁnd more examples in Iliev of the grid, by some integer factor, based on pre-assigned et al. (2009). criteria (Berger & Oliger 1984). The various reﬁnements Enabling AMR in a stand-alone RT code makes it suit- are typically organised in a hierarchical structure connecting able for post-processing the output of many grid-based hy- coarser layers (parent level) with reﬁned layers (child level); dro codes that use the same AMR logic. By representing the grids are then stored and maintained independent from the regions of interest with high resolution grids, we can fol- each other (Berger & Oliger 1984). When the cells that need low the details of the growth of the ionised bubbles around to be reﬁned are clustered together to form disjoint rect- the sources and understand the impact of the RT feedback angular patches, BSAMR schemes are called Patch-based eﬀects on the surrounding environment. A number of stand- (PBAMR; Dai 2010). Both BSAMR and PBAMR involve alone RT codes implementing AMR exist: some examples are reﬁning a speciﬁc region in the grid rather than a single RADAMESH (Cantalupo & Porciani 2011), which is a Monte cell, and so tend to be used synonymously in AMR-related Carlo (MC) RT code with a ray-tracing scheme, and FTTE literature. (Razoumov & Cardall 2005), which implements a scheme to Hereafter, we will limit our discussion to the PBAMR perform RT on reﬁned grids in the presence of diﬀuse and MNRAS 000, 1–18 (2015)

text: Hariharan

text: N.

text: et

text: al.

text: extent

text: by

text: the

text: use

text: of

text: Adaptive

text: Mesh

text: Reﬁnement

text: (AMR)

text: point

text: sources.

text: A

text: ﬁnal

text: example

text: is

text: IFT

text: (Alvarez

text: et

text: al.

text: schemes

text: (e.g.

text: Kravtsov

text: et

text: al.

text: Teyssier

text: Miniati

text: which

text: has

text: been

text: developed

text: to

text: explicitly

text: follow

text: the

text: I-front

text: Colella

text: Bryan

text: et

text: al.

text: which

text: provide

text: a

text: great

text: around

text: a

text: point

text: source.

text: amount

text: of

text: theoretical

text: and

text: algorithmic

text: resources,

text: and

text: have

text: From

text: the

text: above

text: examples,

text: it

text: is

text: clear

text: that

text: AMR-enabled

text: been

text: used

text: extensively

text: to

text: solve

text: a

text: wide

text: range

text: of

text: problems,

text: stand-alone

text: RT

text: codes

text: are

text: increasingly

text: in

text: use

text: and

text: they

text: stand

text: such

text: as

text: numerical

text: relativity,

text: global

text: weather

text: and

text: nuclear

text: fu-

text: to

text: beneﬁt

text: from

text: the

text: advantages

text: that

text: AMR

text: provides.

text: Keep-

text: sion

text: modelling

text: (e.g.

text: Plewa

text: et

text: al.

text: ing

text: this

text: in

text: mind,

text: we

text: have

text: developed

text: CRASH-AMR,

text: a

text: novel

text: AMR

text: schemes

text: use

text: a

text: mesh

text: or

text: a

text: grid

text: to

text: describe

text: the

text: phys-

text: implementation

text: of

text: the

text: RT

text: code

text: CRASH

text: (Ciardi

text: et

text: al.

text: ical

text: domain

text: and

text: to

text: progressively

text: increase

text: the

text: grid

text: resolution

text: Maselli

text: et

text: al.

text: Maselli

text: Ferrara

text: Maselli

text: et

text: al.

text: in

text: conﬁned

text: regions

text: of

text: the

text: mesh,

text: based

text: on

text: a

text: set

text: of

text: reﬁnement

text: Pierleoni

text: et

text: al.

text: Partl

text: et

text: al.

text: Graziani

text: et

text: al.

text: criteria.

text: By

text: selectively

text: increasing

text: the

text: resolution

text: only

text: in

text: the

text: which

text: is

text: interfaced

text: with

text: the

text: open

text: source

text: AMR

text: library

text: interesting

text: part

text: of

text: the

text: domain,

text: AMR

text: methods

text: optimise

text: the

text: CHOMBO

text: (Adams

text: et

text: al.

text: to

text: perform

text: RT

text: simulations

text: on

text: global

text: memory

text: and

text: computational

text: resource

text: requirements.

text: AMR

text: grids.

text: The

text: aim

text: of

text: this

text: paper

text: is

text: to

text: introduce

text: this

text: new

text: The

text: original

text: idea

text: of

text: AMR

text: was

text: to

text: introduce

text: a

text: ﬁner

text: grid

text: in

text: version,

text: to

text: discuss

text: its

text: implementation

text: details

text: and

text: to

text: show

text: regions

text: of

text: higher

text: numerical

text: error,

text: which

text: can

text: be

text: identiﬁed

text: by

text: the

text: tests

text: that

text: we

text: have

text: done

text: to

text: verify

text: and

text: validate

text: CRASH-AMR.

text: density

text: gradients

text: or

text: by

text: Richardson

text: extrapolation

text: (Berger

text: The

text: paper

text: is

text: structured

text: as

text: follows.

text: In

text: Section

text: we

text: brieﬂy

text: Oliger

text: Berger

text: Colella

text: However,

text: AMR

text: can

text: introduce

text: AMR

text: and

text: its

text: diﬀerent

text: schemes,

text: the

text: CHOMBO

text: library

text: be

text: employed

text: very

text: ﬂexibly,

text: and

text: diﬀerent

text: reﬁnement

text: criteria

text: is

text: also

text: presented

text: in

text: this

text: context

text: and

text: we

text: mention

text: some

text: of

text: its

text: can

text: be

text: chosen.

text: For

text: example,

text: in

text: cosmological

text: applications

text: it

text: applications.

text: In

text: Section

text: we

text: introduce

text: the

text: ray

text: tracing

text: im-

text: is

text: customary

text: to

text: adopt

text: a

text: Lagrangian

text: criterion

text: in

text: which

text: cells

text: plementation

text: in

text: the

text: CRASH

text: code.

text: In

text: Section

text: we

text: discuss

text: the

text: are

text: reﬁned

text: when

text: their

text: mass

text: is

text: above

text: a

text: given

text: threshold

text: (e.g.

text: method

text: used

text: to

text: couple

text: CRASH

text: and

text: CHOMBO

text: to

text: enable

text: AMR

text: in

text: Wise

text: Abel

text: Alternatively,

text: it

text: is

text: also

text: possible

text: to

text: reﬁne

text: CRASH.

text: The

text: tests

text: performed

text: to

text: verify

text: our

text: code

text: are

text: discussed

text: speciﬁc

text: volumes

text: in

text: a

text: Eulerian

text: style,

text: which

text: is

text: advantageous

text: in

text: Section

text: and

text: the

text: results

text: are

text: summarised

text: in

text: Section

text: The

text: for

text: example

text: if

text: one

text: is

text: interested

text: in

text: resolving

text: turbulent

text: mo-

text: advantages

text: of

text: the

text: code

text: in

text: terms

text: of

text: computational

text: costs

text: is

text: tions

text: inside

text: cosmological

text: halos

text: (e.g.

text: Miniati

text: highlighted

text: in

text: Appendix

text: and

text: Here,

text: we

text: discuss

text: the

text: tests

text: AMR

text: is

text: also

text: very

text: ﬂexible

text: from

text: an

text: algorithmic

text: point

text: done

text: to

text: show

text: the

text: dependence

text: on

text: grid-resolution

text: and

text: perfor-

text: of

text: view.

text: For

text: example,

text: it

text: naturally

text: supports

text: divergence-

text: mance

text: of

text: the

text: code.

text: We

text: discuss

text: code

text: performance

text: in

text: terms

text: of

text: free

text: magnetohydrodynamics

text: (e.g.

text: Miniati

text: Martin

text: run-time

text: and

text: correctness

text: of

text: results

text: when

text: compared

text: to

text: run-

text: Teyssier

text: et

text: al.

text: Lee

text: Deane

text: it

text: has

text: been

text: used

text: ning

text: RT

text: simulations

text: on

text: uniform

text: grids.

text: to

text: make

text: detailed

text: studies

text: of

text: thermonuclear

text: ﬂashes

text: in

text: FLASH

text: BASICS

text: OF

text: AMR

text: AND

text: THE

text: CHOMBO

text: (Fryxell

text: et

text: al.

text: and

text: also

text: to

text: simulate

text: the

text: formation

text: of

text: LIBRARY

text: large-scale

text: cosmological

text: structures

text: in

text: ENZO

text: (see

text: e.g.

text: Bryan

text: AMR

text: is

text: a

text: successful

text: technique

text: when

text: a

text: problem

text: presents

text: et

text: al.

text: and

text: Plewa

text: et

text: al.

text: for

text: more

text: examples).

text: a

text: highly

text: inhomogeneous

text: spatial

text: distribution

text: implying

text: that

text: Many

text: hydro

text: codes

text: make

text: use

text: of

text: AMR

text: schemes

text: to

text: carry

text: some

text: regions

text: require

text: additional

text: resolution,

text: i.e.

text: additional

text: re-

text: out

text: gas

text: dynamic

text: simulations

text: over

text: a

text: range

text: of

text: spatial

text: scales.

text: ﬁnement.

text: An

text: AMR

text: mesh

text: is

text: deﬁned

text: as

text: structured

text: (SAMR)

text: Some

text: of

text: them

text: are

text: also

text: coupled

text: with

text: RT

text: schemes

text: to

text: per-

text: if

text: its

text: cells

text: (typically

text: cartesian)

text: are

text: connected

text: in

text: a

text: regu-

text: form

text: self-consistent

text: simulations

text: where

text: the

text: RT

text: feedback

text: lar

text: geometry.

text: Un-structured

text: grids

text: composed

text: of

text: triangular

text: is

text: accounted

text: for

text: in

text: the

text: dynamical

text: evolution

text: of

text: the

text: gas.

text: or

text: tetrahedral

text: cells

text: without

text: a

text: regular

text: connectivity

text: can

text: also

text: The

text: Hydrodynamics

text: Adaptive

text: Reﬁnement

text: Tree

text: (HART)

text: code

text: be

text: deﬁned

text: (see

text: for

text: example

text: Mavriplis

text: Khokhlov

text: (Gnedin

text: et

text: al.

text: uses

text: the

text: OTVET

text: approximation

text: for

text: the

text: Springel

text: and

text: Paardekooper

text: et

text: al.

text: We

text: limit

text: our

text: RT

text: implementation

text: (Gnedin

text: Abel

text: while

text: the

text: cos-

text: discussion

text: to

text: SAMR

text: schemes

text: in

text: this

text: paper.

text: mological

text: hydrodynamics

text: code

text: RAMSES

text: (Rosdahl

text: et

text: al.

text: There

text: are

text: many

text: alternative

text: ways

text: to

text: reﬁne

text: a

text: certain

text: sub-

text: designed

text: for

text: simulations

text: of

text: structure

text: formation,

text: incorporates

text: domain

text: using

text: diﬀerent

text: SAMR

text: schemes.

text: In

text: the

text: Cell-based

text: RT

text: using

text: the

text: closure

text: formalism

text: (Levermore

text: Both

text: (CBAMR)

text: scheme

text: each

text: cell

text: of

text: the

text: grid

text: is

text: reﬁned

text: as

text: and

text: when

text: HART

text: and

text: RAMSES

text: make

text: use

text: of

text: the

text: the

text: Fully

text: Threaded

text: Tree

text: required

text: and

text: generally

text: a

text: quad-tree

text: or

text: and

text: oct-tree

text: described

text: in

text: Khokhlov

text: to

text: implement

text: AMR.

text: For

text: the

text: forms

text: the

text: hierarchical

text: structure

text: relating

text: the

text: “coarser”

text: (par-

text: RT

text: ENZO

text: uses

text: an

text: adaptive

text: ray-tracing

text: scheme

text: implemented

text: ent)

text: and

text: “ﬁner”

text: (child)

text: cells

text: (Young

text: et

text: al.

text: The

text: Block-

text: in

text: the

text: HEALPix

text: library

text: (Abel

text: Wandelt

text: Go´rski

text: et

text: al.

text: structured

text: AMR

text: (BSAMR)

text: scheme

text: tags

text: and

text: reﬁnes

text: a

text: region

text: The

text: interested

text: reader

text: can

text: ﬁnd

text: more

text: examples

text: in

text: Iliev

text: of

text: the

text: grid,

text: by

text: some

text: integer

text: factor,

text: based

text: on

text: pre-assigned

text: et

text: al.

text: criteria

text: (Berger

text: Oliger

text: The

text: various

text: reﬁnements

text: Enabling

text: AMR

text: in

text: a

text: stand-alone

text: RT

text: code

text: makes

text: it

text: suit-

text: are

text: typically

text: organised

text: in

text: a

text: hierarchical

text: structure

text: connecting

text: able

text: for

text: post-processing

text: the

text: output

text: of

text: many

text: grid-based

text: hy-

text: coarser

text: layers

text: (parent

text: level)

text: with

text: reﬁned

text: layers

text: (child

text: level);

text: dro

text: codes

text: that

text: use

text: the

text: same

text: AMR

text: logic.

text: By

text: representing

text: the

text: grids

text: are

text: then

text: stored

text: and

text: maintained

text: independent

text: from

text: the

text: regions

text: of

text: interest

text: with

text: high

text: resolution

text: grids,

text: we

text: can

text: fol-

text: each

text: other

text: (Berger

text: Oliger

text: When

text: the

text: cells

text: that

text: need

text: low

text: the

text: details

text: of

text: the

text: growth

text: of

text: the

text: ionised

text: bubbles

text: around

text: to

text: be

text: reﬁned

text: are

text: clustered

text: together

text: to

text: form

text: disjoint

text: rect-

text: the

text: sources

text: and

text: understand

text: the

text: impact

text: of

text: the

text: RT

text: feedback

text: angular

text: patches,

text: BSAMR

text: schemes

text: are

text: called

text: Patch-based

text: eﬀects

text: on

text: the

text: surrounding

text: environment.

text: A

text: number

text: of

text: stand-

text: (PBAMR;

text: Dai

text: Both

text: BSAMR

text: and

text: PBAMR

text: involve

text: alone

text: RT

text: codes

text: implementing

text: AMR

text: exist:

text: some

text: examples

text: are

text: reﬁning

text: a

text: speciﬁc

text: region

text: in

text: the

text: grid

text: rather

text: than

text: a

text: single

text: RADAMESH

text: (Cantalupo

text: Porciani

text: which

text: is

text: a

text: Monte

text: cell,

text: and

text: so

text: tend

text: to

text: be

text: used

text: synonymously

text: in

text: AMR-related

text: Carlo

text: (MC)

text: RT

text: code

text: with

text: a

text: ray-tracing

text: scheme,

text: and

text: FTTE

text: literature.

text: (Razoumov

text: Cardall

text: which

text: implements

text: a

text: scheme

text: to

text: Hereafter,

text: we

text: will

text: limit

text: our

text: discussion

text: to

text: the

text: PBAMR

text: perform

text: RT

text: on

text: reﬁned

text: grids

text: in

text: the

text: presence

text: of

text: diﬀuse

text: and

text: MNRAS


text: Enabling Radiative Transfer on AMR grids in CRASH 19 1 U512 R512 0.8 0.6 0.4 0.2 0 1 U512 R512 0.8 0.6 0.4 0.2 0 1 U512 0.8 R512 0.6 0.4 0.2 0 0 5 10 15 20 25 d [Mpc] Figure B2. LOSs in random directions from a point source for Test 2a at time t = 500 Myr. The lines refer to CRASH-AMR with a uniform grid (solid black) and with 3 r.l. (dashed red). MNRAS 000, 1–18 (2015) x x x IIH IIH IIH ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Enabling

label: title

text: Radiative

text: Transfer

text: on

text: AMR

text: grids

text: in

text: CRASH

font: default

text: d

text: [Mpc]

text: Figure

text: LOSs

label: caption

text: in

text: random

text: directions

text: from

text: a

text: point

text: source

text: for

text: Test

text: at

text: time

text: t

text: Myr.

text: The

text: lines

text: refer

text: to

text: CRASH-AMR

text: with

text: a

text: uniform

text: grid

text: (solid

text: black)

text: and

text: with

text: r.l.

text: (dashed

text: red).

text: MNRAS

text: x

text: x

text: x

text: IIH

text: IIH

text: IIH

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##