text: APPROXIMATE DECONVOLUTION LARGE EDDY SIMULATIONS 25 (a) N = 2 (b) N = 5 Figure 17. Time series of total enstrophy for the hyper- diﬀerential ﬁlters (m = 4). (a) N = 2 (b) N = 5 Figure 18. The third-order structure functions at t = 10 for the hyper-diﬀerential ﬁlters (m = 4). ≤ ≤ coeﬃcients are averaged over the time interval 8 t 12. For N = 2, γ = 1.0 yields the best results. For N = 5, γ = 1.0 yields again the best results. Comparing the N = 2 results with the N = 5 results, the combination γ = 1.0 and N = 2 yields the best results. As expected, the No-AD performs the worst for both N = 2 and N = 5. Increasing N results in a consistent signiﬁcant decrease of the correlation coeﬃcients for all values of the parameter γ. In general, the correlation coeﬃcients of the velocity components are higher than those of the vorticity components. Based on the results in Figs. 15 and 16 and Tables 5 and 6, we conclude that the AD-DF with γ = 1.0 and N = 2 yields the best overall results. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: APPROXIMATE

text: DECONVOLUTION

text: LARGE

text: EDDY

text: SIMULATIONS

text: (a)

text: N

text: (b)

text: N

text: Figure

text: Time

text: series

text: of

text: total

text: enstrophy

text: for

text: the

text: hyper-

text: diﬀerential

text: ﬁlters

text: (m

text: (a)

text: N

text: (b)

text: N

text: Figure

text: The

text: third-order

text: structure

text: functions

text: at

text: t

text: for

text: the

text: hyper-diﬀerential

text: ﬁlters

text: (m

text: coeﬃcients

text: are

text: averaged

text: over

text: the

text: time

text: interval

text: t

text: For

text: N

text: γ

text: yields

text: the

text: best

text: results.

text: For

text: N

text: γ

text: yields

text: again

text: the

text: best

text: results.

text: Comparing

text: the

text: N

text: results

text: with

text: the

text: N

text: results,

text: the

text: combination

text: γ

text: and

text: N

text: yields

text: the

text: best

text: results.

text: As

text: expected,

text: the

text: No-AD

text: performs

text: the

text: worst

text: for

text: both

text: N

text: and

text: N

text: Increasing

text: N

text: results

text: in

text: a

text: consistent

text: signiﬁcant

text: decrease

text: of

text: the

text: correlation

text: coeﬃcients

text: for

text: all

text: values

text: of

text: the

text: parameter

text: γ.

text: In

text: general,

text: the

text: correlation

text: coeﬃcients

text: of

text: the

text: velocity

text: components

text: are

text: higher

text: than

text: those

text: of

text: the

text: vorticity

text: components.

text: Based

text: on

text: the

text: results

text: in

text: Figs.

text: and

text: and

text: Tables

text: and

text: we

text: conclude

text: that

text: the

text: AD-DF

text: with

text: γ

text: and

text: N

text: yields

text: the

text: best

text: overall

text: results.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: APPROXIMATE DECONVOLUTION LARGE EDDY SIMULATIONS 29 (a) N = 2 (b) N = 5 Figure 21. Time series of total enstrophy for the hyper- diﬀerential ﬁlters (m = 16). Fig. 20 presents the third-order structure function deﬁned in (47) for the AD- HDF-8 with N = 2 and N = 5 at t = 10. Results for the DNS and No-AD are also included for comparison purposes. For N = 2, γ = 1.0 yields the best results. For N = 5, γ = 1.0 yields again the best results.. Comparing the N = 2 plot with the N = 5 plot, γ = 1.0 together with N = 2 yields the best results. As expected, the No-AD performs the worst for both N = 2 and N = 5. Table 9 presents the L2-norm of the error of the AD-HDF-8 for N = 2 and N = 5. Results for the No-AD are also included for comparison purposes. The ≤ ≤ errors are averaged over the time interval 8 t 12. For N = 2, γ = 0.8 yields the best results. For N = 5, γ = 1.0 yields the best results. Comparing the N = 2 results with the N = 5 results, γ = 1.0 together with N = 5 yields the best results. As expected, the No-AD performs the worst. Increasing N results in a consistent signiﬁcant increase of the error for γ = 0.6, no trend for γ = 0.8, and a consistent decrease for γ = 1.0. In general, the errors of the velocity components are lower than those of the vorticity components. Table 10 presents the correlation coeﬃcients for the AD-HDF-8 for N = 2 and N = 5. Results for the No-AD are also included for comparison purposes. The ≤ ≤ correlation coeﬃcients are averaged over the time interval 8 t 12. For N = 2, γ = 0.8 yields the best results. For N = 5, γ = 1.0 and γ = 0.8 yield the best results. Comparing the N = 2 results with the N = 5 results, the combination γ = 1.0 and N = 5 yields the best results. As expected, the No-AD performs the worst for both N = 2 and N = 5. Increasing N results in a consistent signiﬁcant decrease of the correlation coeﬃcients for γ = 0.6, no trend for γ = 0.8, and a consistent signiﬁcant increase for γ = 1.0. In general, the correlation coeﬃcients of the velocity components are higher than those of the vorticity components. Based on the results in Figs. 19 and 20 and Tables 9 and 10, we conclude that the AD-HDF-8 with γ = 1.0 and N = 2 or N = 5 yields the best overall results. In this section, we numerically investigate the AD-LES model in conjunction with the hyper-diﬀerential ﬁlter given in (37) and discussed in Section , with m = 16. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: APPROXIMATE

label: paragraph

text: DECONVOLUTION

text: LARGE

text: EDDY

text: SIMULATIONS

text: (a)

text: N

text: (b)

text: N

text: Figure

text: Time

label: caption

text: series

text: of

text: total

text: enstrophy

text: for

text: the

text: hyper-

text: diﬀerential

text: ﬁlters

text: (m

text: Fig.

text: presents

text: the

text: third-order

text: structure

text: function

text: deﬁned

text: in

text: for

text: the

text: AD-

text: with

text: N

text: and

text: N

text: at

text: t

text: Results

text: for

text: the

text: DNS

text: and

text: No-AD

text: are

text: also

text: included

text: for

text: comparison

text: purposes.

text: For

text: N

text: γ

text: yields

text: the

text: best

text: results.

text: For

text: N

text: γ

text: yields

text: again

text: the

text: best

text: results..

text: Comparing

text: the

text: N

text: plot

text: with

text: the

text: N

text: plot,

text: γ

text: together

text: with

text: N

text: yields

text: the

text: best

text: results.

text: As

text: expected,

text: the

text: No-AD

text: performs

text: the

text: worst

text: for

text: both

text: N

text: and

text: N

text: Table

text: presents

text: the

text: of

text: the

text: error

text: of

text: the

text: for

text: N

text: and

text: N

text: Results

text: for

text: the

text: No-AD

text: are

text: also

text: included

text: for

text: comparison

text: purposes.

text: The

text: errors

text: are

text: averaged

text: over

text: the

text: time

text: interval

text: t

text: For

text: N

text: γ

text: yields

text: the

text: best

text: results.

text: For

text: N

text: γ

text: yields

text: the

text: best

text: results.

text: Comparing

text: the

text: N

text: results

text: with

text: the

text: N

text: results,

text: γ

text: together

text: with

text: N

text: yields

text: the

text: best

text: results.

text: As

text: expected,

text: the

text: No-AD

text: performs

text: the

text: worst.

text: Increasing

text: N

text: results

text: in

text: a

text: consistent

text: signiﬁcant

text: increase

text: of

text: the

text: error

text: for

text: γ

text: no

text: trend

text: for

text: γ

text: and

text: a

text: consistent

text: decrease

text: for

text: γ

text: In

text: general,

text: the

text: errors

text: of

text: the

text: velocity

text: components

text: are

text: lower

text: than

text: those

text: of

text: the

text: vorticity

text: components.

text: Table

text: presents

text: the

text: correlation

text: coeﬃcients

text: for

text: the

text: for

text: N

text: and

text: N

text: Results

text: for

text: the

text: No-AD

text: are

text: also

text: included

text: for

text: comparison

text: purposes.

text: The

text: correlation

text: coeﬃcients

text: are

text: averaged

text: over

text: the

text: time

text: interval

text: t

text: For

text: N

text: γ

text: yields

text: the

text: best

text: results.

text: For

text: N

text: γ

text: and

text: γ

text: yield

text: the

text: best

text: results.

text: Comparing

text: the

text: N

text: results

text: with

text: the

text: N

text: results,

text: the

text: combination

text: γ

text: and

text: N

text: yields

text: the

text: best

text: results.

text: As

text: expected,

text: the

text: No-AD

text: performs

text: the

text: worst

text: for

text: both

text: N

text: and

text: N

text: Increasing

text: N

text: results

text: in

text: a

text: consistent

text: signiﬁcant

text: decrease

text: of

text: the

text: correlation

text: coeﬃcients

text: for

text: γ

text: no

text: trend

text: for

text: γ

text: and

text: a

text: consistent

text: signiﬁcant

text: increase

text: for

text: γ

text: In

text: general,

text: the

text: correlation

text: coeﬃcients

text: of

text: the

text: velocity

text: components

text: are

text: higher

text: than

text: those

text: of

text: the

text: vorticity

text: components.

text: Based

text: on

text: the

text: results

text: in

text: Figs.

text: and

text: and

text: Tables

text: and

text: we

text: conclude

text: that

text: the

text: with

text: γ

text: and

text: N

text: or

text: N

text: yields

text: the

text: best

text: overall

text: results.

text: In

text: this

text: section,

text: we

text: numerically

text: investigate

text: the

text: AD-LES

text: model

text: in

text: conjunction

text: with

text: the

text: hyper-diﬀerential

text: ﬁlter

text: given

text: in

text: and

text: discussed

text: in

text: Section

text: with

text: m

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 30 O. SAN, A. E. STAPLES, AND T. ILIESCU (a) N = 2 (b) N = 5 Figure 22. The third-order structure functions at t = 10 for the hyper-diﬀerential ﬁlters (m = 16). Table 11. Discrete L2-norms using the hyper-diﬀerential ﬁlters for m = 16 (with resolutions of 643) for ensemble averaging the data on a time interval between t = 8 and t = 12. The reference solution for computing the L2-norm is the DNS data obtained with a resolution of 2563. Field No-AD HDF(m = 16, γ = 0.6) HDF(m = 16, γ = 0.8) HDF(m = 16, γ = 1.0) N = 2 N = 5 N = 2 N = 5 N = 2 N = 5 u 0.151 0.092 0.096 0.065 0.066 0.073 0.072 v 0.169 0.090 0.094 0.063 0.065 0.078 0.073 w 0.166 0.100 0.103 0.077 0.079 0.093 0.092 ω 1.233 0.656 0.669 0.549 0.560 0.620 0.597 x ω 1.001 0.652 0.656 0.594 0.582 0.639 0.602 y ω 1.307 0.569 0.585 0.437 0.434 0.465 0.459 z Table 12. Correlation coeﬃcient between the DNS data (with a resolution of 2563) and AD results with the hyper-diﬀerential ﬁlters (with resolutions of 643) for the power m = 16 for ensemble averaging on a time interval between t = 8 and t = 12. Correlation coeﬃcients between the DNS and No-AD model (with a resolution of 643) are also listed for comparison purposes. Field C(DNS, No-AD) C(DNS, γ = 0.6) C(DNS, γ = 0.8) C(DNS, γ = 1.0) N = 2 N = 5 N = 2 N = 5 N = 2 N = 5 u 0.692 0.885 0.874 0.938 0.939 0.907 0.909 v 0.528 0.823 0.805 0.927 0.921 0.892 0.908 w 0.552 0.786 0.780 0.819 0.809 0.733 0.729 ω 0.342 0.685 0.674 0.744 0.732 0.657 0.668 x ω 0.410 0.639 0.636 0.685 0.696 0.624 0.650 y ω 0.277 0.627 0.617 0.729 0.729 0.656 0.663 z ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: O.

text: SAN,

text: A.

text: E.

text: STAPLES,

text: AND

text: T.

text: ILIESCU

text: (a)

text: N

text: (b)

text: N

text: Figure

text: The

text: third-order

text: structure

text: functions

text: at

text: t

text: for

text: the

text: hyper-diﬀerential

text: ﬁlters

text: (m

text: Table

text: Discrete

text: using

text: the

text: hyper-diﬀerential

text: ﬁlters

text: for

text: m

text: (with

text: resolutions

text: of

text: for

text: ensemble

text: averaging

text: the

text: data

text: on

text: a

text: time

text: interval

text: between

text: t

text: and

text: t

text: The

text: reference

text: solution

text: for

text: computing

text: the

text: is

text: the

text: DNS

text: data

text: obtained

text: with

text: a

text: resolution

text: of

text: Field

label: table

text: No-AD

text: HDF(m

text: γ

text: HDF(m

text: γ

text: HDF(m

text: γ

text: N

text: N

text: N

text: N

text: N

text: N

text: u

text: v

text: w

text: ω

text: x

text: ω

text: y

text: ω

text: z

text: Table

text: Correlation

text: coeﬃcient

text: between

text: the

text: DNS

text: data

text: (with

text: a

text: resolution

text: of

text: and

text: AD

text: results

text: with

text: the

text: hyper-diﬀerential

text: ﬁlters

text: (with

text: resolutions

text: of

text: for

text: the

text: power

text: m

text: for

text: ensemble

text: averaging

text: on

text: a

text: time

text: interval

text: between

text: t

text: and

text: t

text: Correlation

text: coeﬃcients

text: between

text: the

text: DNS

text: and

text: No-AD

text: model

text: (with

text: a

text: resolution

text: of

text: are

text: also

text: listed

text: for

text: comparison

text: purposes.

text: Field

text: C(DNS,

text: No-AD)

text: C(DNS,

text: γ

text: C(DNS,

text: γ

text: C(DNS,

text: γ

text: N

text: N

text: N

text: N

text: N

text: N

text: u

text: v

text: w

text: ω

text: x

text: ω

text: y

text: ω

text: z

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 16 Omer San, Traian Iliescu (a) ω (t = 40) (b) ω (t = 60) (c) ω (t = 80) (d) ψ (t = 40) (e) ψ (t = 60) (f) ψ (t = 80) Fig. 3 Instantaneous vorticity (a-c) and stream function (d-f) contour plots for Experiment 2. in our study, a grid resolution of N > 50 in the x direction (L is the basin x dimension in x direction) represents the Munk layer resolving computation. Therefore, we use the Munk layer resolving computations as a reference solu- tion which is denoted here as DNS. We emphasize that the term DNS in this study is not meant to indicate that a fully detailed solution is being computed on the molecular viscosity scale, but instead refers to resolving the simulation down to the Munk scale via the speciﬁed lateral eddy viscosity parameteri- zation (e.g., see [45] for details). All numerical experiments conducted here are solved for a maximum dimensionless time of T = 80. This value cor- max responds to the dimensional times of 20.12 and 45.28 years for Experiment 1 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine##

text: Omer

label: author

text: San,

text: Traian

text: Iliescu

text: (a)

text: ω

text: (t

text: (b)

text: ω

text: (t

text: (c)

text: ω

text: (t

text: (d)

text: ψ

text: (t

text: (e)

text: ψ

text: (t

text: (f)

text: ψ

text: (t

text: Fig.

text: Instantaneous

text: vorticity

text: (a-c)

text: and

text: stream

text: function

text: (d-f)

text: contour

text: plots

text: for

text: Experiment

text: in

text: our

text: study,

text: a

text: grid

text: resolution

text: of

text: N

text: in

text: the

text: x

text: direction

text: (L

text: is

text: the

text: basin

text: x

text: dimension

text: in

text: x

text: direction)

text: represents

text: the

text: Munk

text: layer

text: resolving

text: computation.

text: Therefore,

text: we

text: use

text: the

text: Munk

text: layer

text: resolving

text: computations

text: as

text: a

text: reference

text: solu-

text: tion

text: which

text: is

text: denoted

text: here

text: as

text: DNS.

text: We

text: emphasize

text: that

text: the

text: term

text: DNS

text: in

text: this

text: study

text: is

text: not

text: meant

text: to

text: indicate

text: that

text: a

text: fully

text: detailed

text: solution

text: is

text: being

text: computed

text: on

text: the

text: molecular

text: viscosity

text: scale,

text: but

text: instead

text: refers

text: to

text: resolving

text: the

text: simulation

text: down

text: to

text: the

text: Munk

text: scale

text: via

text: the

text: speciﬁed

text: lateral

text: eddy

text: viscosity

text: parameteri-

text: zation

text: (e.g.,

text: see

text: for

text: details).

text: All

text: numerical

text: experiments

text: conducted

text: here

text: are

text: solved

text: for

text: a

text: maximum

text: dimensionless

text: time

text: of

text: T

text: This

text: value

text: cor-

text: max

text: responds

text: to

text: the

text: dimensional

text: times

text: of

text: and

text: years

text: for

text: Experiment

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##


text: 18 Omer San, Traian Iliescu (a) k = 1 (b) k = 5 (c) k = 10 (d) k = 15 (e) k = 20 (f) k = 30 Fig. 5 Illustrative examples of POD basis functions, ϕ , for Experiment 1. k and Experiment 2, respectively, which are long enough to capture statistically steady states. To assess the POD-ROM, we employ the standard model reduction method- ology. POD starts with data from an accurate numerical solution of underlying governing equation. The BVE equation is solved for the four-gyre problems by using the fourth-order Arakawa scheme for spatial derivatives and the third- order Runge-Kutta schemes for the time advancement process. We ﬁrst run × DNS computations on a ﬁne mesh by using the resolution of 256 512 with × − a time step of ∆t = 2.5 10 5. After a transient initial period, the ﬂow ex- hibits a quasi-stationary regime for the present conﬁgurations. We store 700 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine##

text: Omer

text: San,

text: Traian

text: Iliescu

text: (a)

text: k

text: (b)

text: k

text: (c)

text: k

text: (d)

text: k

text: (e)

text: k

text: (f)

text: k

text: Fig.

text: Illustrative

text: examples

text: of

text: POD

text: basis

text: functions,

text: ϕ

text: for

text: Experiment

text: k

text: and

text: Experiment

text: respectively,

text: which

text: are

text: long

text: enough

text: to

text: capture

text: statistically

text: steady

text: states.

text: To

text: assess

text: the

text: POD-ROM,

text: we

text: employ

text: the

text: standard

text: model

text: reduction

text: method-

text: ology.

text: POD

text: starts

text: with

text: data

text: from

text: an

text: accurate

text: numerical

text: solution

text: of

text: underlying

text: governing

text: equation.

text: The

text: BVE

text: equation

text: is

text: solved

text: for

text: the

text: four-gyre

text: problems

text: by

text: using

text: the

text: fourth-order

text: Arakawa

text: scheme

text: for

text: spatial

text: derivatives

text: and

text: the

text: third-

text: order

text: Runge-Kutta

text: schemes

text: for

text: the

text: time

text: advancement

text: process.

text: We

text: ﬁrst

text: run

text: DNS

text: computations

text: on

text: a

text: ﬁne

text: mesh

text: by

text: using

text: the

text: resolution

text: of

text: with

text: a

text: time

text: step

text: of

text: ∆t

text: After

text: a

text: transient

text: initial

text: period,

text: the

text: ﬂow

text: ex-

text: hibits

text: a

text: quasi-stationary

text: regime

text: for

text: the

text: present

text: conﬁgurations.

text: We

text: store

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##


text: 24 Omer San, Traian Iliescu a standard prototype of more realistic ocean dynamics, where a symmetric double-gyre wind forcing yields four-gyre circulations in the time mean. To re- duce the error associated with the numerical discretization, we used a fourth- order Arakawa scheme for the spatial discretization and a third-order Runge- Kutta scheme for the temporal integration. Two numerical examples were used to assess the performance of the POD-ROMs. We constructed diﬀerent ROMs with diﬀerent numbers of POD basis functions and stabilization parameters. Results obtained from these POD-ROMs were compared with those calculated by DNS. We showed that the large scale quasigeostropic dynamics are well captured by the proposed POD-ROM even with a few modes. The stabilized POD- ROM yielded numerical results that were in close agreement with those of the DNS. In particular, the four gyre structure of the time-averaged stream func- tion contour plots was recovered by the proposed POD-ROM. Using the same number of modes as the stabilized POD-ROM, the standard Galerkin POD- ROM produced inaccurate, unphysical results. We also performed a numerical investigation of the sensitivity with respect to the free stabilization parame- ters used and we found that the stabilized POD-ROM is robust. This ﬁrst step in the numerical assessment of the proposed POD-ROM shows that it could represent a viable model reduction tool in numerical weather prediction and climate modeling. References 1. Amsallem, D., Farhat, C.: Stabilization of projection-based reduced-order models. In- ternational Journal for Numerical Methods in Engineering 91(4), 358–377 (2012) 2. Arakawa, A.: Computational design for long-term numerical integration of the equations of ﬂuid motion: Two-dimensional incompressible ﬂow. Part I. Journal of Computational Physics 1(1), 119–143 (1966) 3. Balajewicz, M.J., Dowell, E.H., Noack, B.R.: Low-dimensional modelling of high- Reynolds-number shear ﬂows incorporating constraints from the Navier–Stokes equa- tion. Journal of Fluid Mechanics 729, 285–308 (2013) 4. Bergmann, M., Bruneau, C.H., Iollo, A.: Enablers for robust POD models. Journal of Computational Physics 228(2), 516–538 (2009) 5. Briley, W.R.: A numerical study of laminar separation bubbles using the Navier-Stokes equations. Journal of Fluid Mechanics 47(4), 713–736 (1971) 6. Bui-Thanh, T., Willcox, K., Ghattas, O.: Model reduction for large-scale systems with high-dimensional parametric input space. SIAM Journal on Scientiﬁc Computing 30(6), 3270–3288 (2008) 7. Cao, Y., Zhu, J., Navon, I.M., Luo, Z.: A reduced-order approach to four-dimensional variational data assimilation using proper orthogonal decomposition. International Jour- nal for Numerical Methods in Fluids 53(10), 1571–1583 (2007) 8. Carlberg, K., Bou-Mosleh, C., Farhat, C.: Eﬃcient non-linear model reduction via a least-squares Petrov–Galerkin projection and compressive tensor approximations. In- ternational Journal for Numerical Methods in Engineering 86(2), 155–181 (2011) 9. Cazemier, W.: Proper orthogonal decomposition and low dimensional models for tur- bulent ﬂows. Ph.D. thesis, Rijksuniversiteit Groningen (1997) 10. Couplet, M., Sagaut, P., Basdevant, C.: Intermodal energy transfers in a proper orthog- onal decomposition-Galerkin representation of a turbulent separated ﬂow. Journal of Fluid Mechanics 491, 275–284 (2003) 11. Crommelin, D.T., Majda, A.J.: Strategies for model reduction: comparing diﬀerent op- timal bases. Journal of the Atmospheric Sciences 61, 2206–2217 (2004) 12. Cummins, P.F.: Inertial gyres in decaying and forced geostrophic turbulence. Journal of Marine Research 50(4), 545–566 (1992) ##LTLine##

text: Omer

text: San,

text: Traian

text: Iliescu

text: a

text: standard

text: prototype

text: of

text: more

text: realistic

text: ocean

text: dynamics,

text: where

text: a

text: symmetric

text: double-gyre

text: wind

text: forcing

text: yields

text: four-gyre

text: circulations

text: in

text: the

text: time

text: mean.

text: To

text: re-

text: duce

text: the

text: error

text: associated

text: with

text: the

text: numerical

text: discretization,

text: we

text: used

text: a

text: fourth-

text: order

text: Arakawa

text: scheme

text: for

text: the

text: spatial

text: discretization

text: and

text: a

text: third-order

text: Runge-

text: Kutta

text: scheme

text: for

text: the

text: temporal

text: integration.

text: Two

text: numerical

text: examples

text: were

text: used

text: to

text: assess

text: the

text: performance

text: of

text: the

text: POD-ROMs.

text: We

text: constructed

text: diﬀerent

text: ROMs

text: with

text: diﬀerent

text: numbers

text: of

text: POD

text: basis

text: functions

text: and

text: stabilization

text: parameters.

text: Results

text: obtained

text: from

text: these

text: POD-ROMs

text: were

text: compared

text: with

text: those

text: calculated

text: by

text: DNS.

text: We

text: showed

text: that

text: the

text: large

text: scale

text: quasigeostropic

text: dynamics

text: are

text: well

text: captured

text: by

text: the

text: proposed

text: POD-ROM

text: even

text: with

text: a

text: few

text: modes.

text: The

text: stabilized

text: POD-

text: ROM

text: yielded

text: numerical

text: results

text: that

text: were

text: in

text: close

text: agreement

text: with

text: those

text: of

text: the

text: DNS.

text: In

text: particular,

text: the

text: four

text: gyre

text: structure

text: of

text: the

text: time-averaged

text: stream

text: func-

text: tion

text: contour

text: plots

text: was

text: recovered

text: by

text: the

text: proposed

text: POD-ROM.

text: Using

text: the

text: same

text: number

text: of

text: modes

text: as

text: the

text: stabilized

text: POD-ROM,

text: the

text: standard

text: Galerkin

text: POD-

text: ROM

text: produced

text: inaccurate,

text: unphysical

text: results.

text: We

text: also

text: performed

text: a

text: numerical

text: investigation

text: of

text: the

text: sensitivity

text: with

text: respect

text: to

text: the

text: free

text: stabilization

text: parame-

text: ters

text: used

text: and

text: we

text: found

text: that

text: the

text: stabilized

text: POD-ROM

text: is

text: robust.

text: This

text: ﬁrst

text: step

text: in

text: the

text: numerical

text: assessment

text: of

text: the

text: proposed

text: POD-ROM

text: shows

text: that

text: it

text: could

text: represent

text: a

text: viable

text: model

text: reduction

text: tool

text: in

text: numerical

text: weather

text: prediction

text: and

text: climate

text: modeling.

text: References

text: Amsallem,

text: D.,

text: Farhat,

text: C.:

text: Stabilization

text: of

text: projection-based

text: reduced-order

text: models.

text: In-

text: ternational

text: Journal

text: for

text: Numerical

text: Methods

text: in

text: Engineering

text: Arakawa,

text: A.:

text: Computational

text: design

text: for

text: long-term

text: numerical

text: integration

text: of

text: the

text: equations

text: of

text: ﬂuid

text: motion:

text: Two-dimensional

text: incompressible

text: ﬂow.

text: Part

text: I.

text: Journal

text: of

text: Computational

text: Physics

text: Balajewicz,

text: M.J.,

text: Dowell,

text: E.H.,

text: Noack,

text: B.R.:

text: Low-dimensional

text: modelling

text: of

text: high-

text: Reynolds-number

text: shear

text: ﬂows

text: incorporating

text: constraints

text: from

text: the

text: Navier–Stokes

text: equa-

text: tion.

text: Journal

text: of

text: Fluid

text: Mechanics

text: Bergmann,

text: M.,

text: Bruneau,

text: C.H.,

text: Iollo,

text: A.:

text: Enablers

text: for

text: robust

text: POD

text: models.

text: Journal

text: of

text: Computational

text: Physics

text: Briley,

text: W.R.:

text: A

text: numerical

text: study

text: of

text: laminar

text: separation

text: bubbles

text: using

text: the

text: Navier-Stokes

text: equations.

text: Journal

text: of

text: Fluid

text: Mechanics

text: Bui-Thanh,

text: T.,

text: Willcox,

text: K.,

text: Ghattas,

text: O.:

text: Model

text: reduction

text: for

text: large-scale

text: systems

text: with

text: high-dimensional

text: parametric

text: input

text: space.

text: SIAM

text: Journal

text: on

text: Scientiﬁc

text: Computing

text: Cao,

text: Y.,

text: Zhu,

text: J.,

text: Navon,

text: I.M.,

text: Luo,

text: Z.:

text: A

text: reduced-order

text: approach

text: to

text: four-dimensional

text: variational

text: data

text: assimilation

text: using

text: proper

text: orthogonal

text: decomposition.

text: International

text: Jour-

text: nal

text: for

text: Numerical

text: Methods

text: in

text: Fluids

text: Carlberg,

text: K.,

text: Bou-Mosleh,

text: C.,

text: Farhat,

text: C.:

text: Eﬃcient

text: non-linear

text: model

text: reduction

text: via

text: a

text: least-squares

text: Petrov–Galerkin

text: projection

text: and

text: compressive

text: tensor

text: approximations.

text: In-

text: ternational

text: Journal

text: for

text: Numerical

text: Methods

text: in

text: Engineering

text: Cazemier,

text: W.:

text: Proper

text: orthogonal

text: decomposition

text: and

text: low

text: dimensional

text: models

text: for

text: tur-

text: bulent

text: ﬂows.

text: Ph.D.

text: thesis,

text: Rijksuniversiteit

text: Groningen

text: Couplet,

text: M.,

text: Sagaut,

text: P.,

text: Basdevant,

text: C.:

text: Intermodal

text: energy

text: transfers

text: in

text: a

text: proper

text: orthog-

text: onal

text: decomposition-Galerkin

text: representation

text: of

text: a

text: turbulent

text: separated

text: ﬂow.

text: Journal

text: of

text: Fluid

text: Mechanics

text: Crommelin,

text: D.T.,

text: Majda,

text: A.J.:

text: Strategies

text: for

text: model

text: reduction:

text: comparing

text: diﬀerent

text: op-

text: timal

text: bases.

text: Journal

text: of

text: the

text: Atmospheric

text: Sciences

text: Cummins,

text: P.F.:

text: Inertial

text: gyres

text: in

text: decaying

text: and

text: forced

text: geostrophic

text: turbulence.

text: Journal

text: of

text: Marine

text: Research

text: ##LTLine##


text: 26 Omer San, Traian Iliescu 38. Pedlosky, J.: Geophysical ﬂuid dynamics. New York and Berlin, Springer-Verlag (1982) 39. Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T.: Numerical Recipes in FORTRAN. Cambridge University Press (1992) 40. Ravindran, S.: A reduced-order approach for optimal control of ﬂuids using proper or- thogonal decomposition. International Journal for Numerical Methods in Fluids 34(5), 425–448 (2000) 41. Rempfer, D.: Koherente struturen und chaos beim laminar-turbulenten grenzschichtum- schlag. Ph.D. thesis, University of Stuttgart (1991) 42. Rowley, C.W., Williams, D.R.: Dynamics and control of high-Reynolds-number ﬂow over open cavities. Annual Review of Fluid Mechanics 38, 251–276 (2006) 43. San, O., Staples, A.E.: High-order methods for decaying two-dimensional homogeneous isotropic turbulence. Computers & Fluids 63, 105–127 (2012) 44. San, O., Staples, A.E.: A coarse-grid projection method for accelerating incompressible ﬂow computations. Journal of Computational Physics 233, 480–508 (2013) 45. San, O., Staples, A.E., Iliescu, T.: Approximate deconvolution large eddy simulation of a stratiﬁed two-layer quasigeostrophic ocean model. Ocean Modelling 63, 1–20 (2013) 46. San, O., Staples, A.E., Wang, Z., Iliescu, T.: Approximate deconvolution large eddy simulation of a barotropic ocean circulation model. Ocean Modelling 40(2), 120–132 (2011) 47. Gal´an del Sastre, P., Bermejo, R.: Error estimates of proper orthogonal decomposition eigenvectors and Galerkin projection for a general dynamical system arising in ﬂuid models. Numerische Mathematik 110(1), 49–81 (2008) 48. Selten, F.M.: An eﬃcient description of the dynamics of barotropic ﬂow. Journal of the Atmospheric Sciences 52(7), 915–936 (1995) 49. Sirovich, L.: Turbulence and the dynamics of coherent structures. I-Coherent structures. II-Symmetries and transformations. III-Dynamics and scaling. Quarterly of Applied Mathematics 45, 561–571 (1987) 50. Strikwerda, J.: Finite diﬀerence schemes and partial diﬀerential equations. Society for Industrial and Applied Mathematics (2007) 51. Vallis, G.K.: Atmospheric and oceanic ﬂuid dynamics: fundamentals and large-scale circulation. Cambridge University Press (2006) 52. Wang, Y., Zhang, J.: Sixth order compact scheme combined with multigrid method and extrapolation technique for 2D Poisson equation. Journal of Computational Physics 228(1), 137–146 (2009) 53. Wang, Z., Akhtar, I., Borggaard, J., Iliescu, T.: Two-level discretizations of nonlinear closure models for proper orthogonal decomposition. Journal of Computational Physics 230(1), 126–146 (2011) 54. Wang, Z., Akhtar, I., Borggaard, J., Iliescu, T.: Proper orthogonal decomposition closure models for turbulent ﬂows: a numerical comparison. Computer Methods in Applied Mechanics and Engineering 237–240, 10–26 (2012) 55. Wold, S., Esbensen, K., Geladi, P.: Principal component analysis. Chemometrics and Intelligent Laboratory Systems 2(1), 37–52 (1987) ##LTLine##

text: Omer

text: San,

text: Traian

text: Iliescu

label: reference

text: Pedlosky,

text: J.:

text: Geophysical

text: ﬂuid

text: dynamics.

text: New

text: York

text: and

text: Berlin,

text: Springer-Verlag

text: Press,

text: W.H.,

text: Flannery,

text: B.P.,

text: Teukolsky,

text: S.A.,

text: Vetterling,

text: W.T.:

text: Numerical

text: Recipes

text: in

text: FORTRAN.

text: Cambridge

text: University

text: Press

text: Ravindran,

text: S.:

text: A

text: reduced-order

text: approach

text: for

text: optimal

text: control

text: of

text: ﬂuids

text: using

text: proper

text: or-

text: thogonal

text: decomposition.

text: International

text: Journal

text: for

text: Numerical

text: Methods

text: in

text: Fluids

text: Rempfer,

text: D.:

text: Koherente

text: struturen

text: und

text: chaos

text: beim

text: laminar-turbulenten

text: grenzschichtum-

text: schlag.

text: Ph.D.

text: thesis,

text: University

text: of

text: Stuttgart

text: Rowley,

text: C.W.,

text: Williams,

text: D.R.:

text: Dynamics

text: and

text: control

text: of

text: high-Reynolds-number

text: ﬂow

text: over

text: open

text: cavities.

text: Annual

text: Review

text: of

text: Fluid

text: Mechanics

text: San,

text: O.,

text: Staples,

text: A.E.:

text: High-order

text: methods

text: for

text: decaying

text: two-dimensional

text: homogeneous

text: isotropic

text: turbulence.

text: Computers

text: Fluids

text: San,

text: O.,

text: Staples,

text: A.E.:

text: A

text: coarse-grid

text: projection

text: method

text: for

text: accelerating

text: incompressible

text: ﬂow

text: computations.

text: Journal

text: of

text: Computational

text: Physics

text: San,

text: O.,

text: Staples,

text: A.E.,

text: Iliescu,

text: T.:

text: Approximate

text: deconvolution

text: large

text: eddy

text: simulation

text: of

text: a

text: stratiﬁed

text: two-layer

text: quasigeostrophic

text: ocean

text: model.

text: Ocean

text: Modelling

text: San,

text: O.,

text: Staples,

text: A.E.,

text: Wang,

text: Z.,

text: Iliescu,

text: T.:

text: Approximate

text: deconvolution

text: large

text: eddy

text: simulation

text: of

text: a

text: barotropic

text: ocean

text: circulation

text: model.

text: Ocean

text: Modelling

text: Gal´an

text: del

text: Sastre,

text: P.,

text: Bermejo,

text: R.:

text: Error

text: estimates

text: of

text: proper

text: orthogonal

text: decomposition

text: eigenvectors

text: and

text: Galerkin

text: projection

text: for

text: a

text: general

text: dynamical

text: system

text: arising

text: in

text: ﬂuid

text: models.

text: Numerische

text: Mathematik

text: Selten,

text: F.M.:

text: An

text: eﬃcient

text: description

text: of

text: the

text: dynamics

text: of

text: barotropic

text: ﬂow.

text: Journal

text: of

text: the

text: Atmospheric

text: Sciences

text: Sirovich,

text: L.:

text: Turbulence

text: and

text: the

text: dynamics

text: of

text: coherent

text: structures.

text: I-Coherent

text: structures.

text: II-Symmetries

text: and

text: transformations.

text: III-Dynamics

text: and

text: scaling.

text: Quarterly

text: of

text: Applied

text: Mathematics

text: Strikwerda,

text: J.:

text: Finite

text: diﬀerence

text: schemes

text: and

text: partial

text: diﬀerential

text: equations.

text: Society

text: for

text: Industrial

text: and

text: Applied

text: Mathematics

text: Vallis,

text: G.K.:

text: Atmospheric

text: and

text: oceanic

text: ﬂuid

text: dynamics:

text: fundamentals

text: and

text: large-scale

text: circulation.

text: Cambridge

text: University

text: Press

text: Wang,

text: Y.,

text: Zhang,

text: J.:

text: Sixth

text: order

text: compact

text: scheme

text: combined

text: with

text: multigrid

text: method

text: and

text: extrapolation

text: technique

text: for

text: Poisson

text: equation.

text: Journal

text: of

text: Computational

text: Physics

text: Wang,

text: Z.,

text: Akhtar,

text: I.,

text: Borggaard,

text: J.,

text: Iliescu,

text: T.:

text: Two-level

text: discretizations

text: of

text: nonlinear

text: closure

text: models

text: for

text: proper

text: orthogonal

text: decomposition.

text: Journal

text: of

text: Computational

text: Physics

text: Wang,

text: Z.,

text: Akhtar,

text: I.,

text: Borggaard,

text: J.,

text: Iliescu,

text: T.:

text: Proper

text: orthogonal

text: decomposition

text: closure

text: models

text: for

text: turbulent

text: ﬂows:

text: a

text: numerical

text: comparison.

text: Computer

text: Methods

text: in

text: Applied

text: Mechanics

text: and

text: Engineering

text: Wold,

text: S.,

text: Esbensen,

text: K.,

text: Geladi,

text: P.:

text: Principal

text: component

text: analysis.

text: Chemometrics

text: and

text: Intelligent

text: Laboratory

text: Systems

text: ##LTLine##


text: 4 Omer San, Traian Iliescu oceanic basins. To account for the Earth’s rotational eﬀects, in the beta-plane approximation the Coriolis parameter is approximated by f = f + βy, where 0 f is the constant mean Coriolis parameter and β is the gradient of the Coriolis 0 parameter at the basin center (i.e., y = 0). The nonlinear convection term in Eq. (1), called the nonlinear Jacobian, is deﬁned as ∂ψ ∂ω − ∂ψ ∂ω J(ω, ψ) = . (5) ∂y ∂x ∂x ∂y The viscous dissipation mechanism has the standard form ∇ D = ν 2ω, (6) where ν is the eddy viscosity coeﬃcie(cid:16)nt. T(cid:17)he double-gyre wind forcing function in the model is given by τ π y F = 0 sin π , (7) ρH L L where τ is the maximum amplitude of the double-gyre wind stress, ρ is 0 the mean ﬂuid density, and H is the mean depth of the ocean basin. In order to obtain a dimensionless of the BVE, we use the following deﬁnitions: x y t ω ψ x˜ = , y˜ = , t˜= , ω˜ = , ψ˜ = , (8) L L L/V V/L V L where the tilde denotes the corresponding nondimensional variables. In the nondimensionalization, L represents the characteristic horizontal length scale (in our study L is the basin dimension in the x direction), and V is the characteristic velocity scale. The Sverdrup velocity scale used for nondimen- sionalization can be written in the following form τ π V = 0 . (9) ρH βL Finally, the governing equations for two-dimensional incompressible barotropic quasigeostrophic ﬂows can be written in dimensionless form in beta-plane as the dimensionless BVE ∂ω − 1 ∂ψ 1 ∇ 1 + J(ω, ψ) = 2ω + sin(πy), (10) ∂t Ro ∂x Re Ro where we omit the tilde over the variables for clarity purposes. Due to the nondimensionalization given by Eq. (8), the elliptic subproblem given in Eq. (4) remains the same. In the dimensionless form given in Eq, (10), there are only two nondimensional parameters, Reynolds and Rossby numbers, which are related to the physical parameters in the following way: ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Omer

text: San,

text: Traian

text: Iliescu

text: oceanic

text: basins.

text: To

text: account

text: for

text: the

text: Earth’s

text: rotational

text: eﬀects,

text: in

text: the

text: beta-plane

text: approximation

text: the

text: Coriolis

text: parameter

text: is

text: approximated

text: by

text: f

text: f

text: βy,

text: where

text: f

text: is

text: the

text: constant

text: mean

text: Coriolis

text: parameter

text: and

text: β

text: is

text: the

text: gradient

text: of

text: the

text: Coriolis

text: parameter

text: at

text: the

text: basin

text: center

text: (i.e.,

text: y

text: The

text: nonlinear

text: convection

text: term

text: in

text: Eq.

text: called

text: the

text: nonlinear

text: Jacobian,

text: is

text: deﬁned

text: as

text: ∂ψ

label: equation

text: ∂ω

text: ∂ψ

text: ∂ω

text: J(ω,

text: ψ)

text: ∂y

text: ∂x

text: ∂x

text: ∂y

text: The

text: viscous

text: dissipation

text: mechanism

text: has

text: the

text: standard

text: form

text: D

text: ν

text: where

text: ν

text: is

text: the

text: eddy

text: viscosity

text: double-gyre

text: wind

text: forcing

text: function

text: in

text: the

text: model

text: is

text: given

text: by

text: τ

text: π

text: y

text: F

text: sin

text: π

text: ρH

text: L

text: L

text: where

text: τ

text: is

text: the

text: maximum

text: amplitude

text: of

text: the

text: double-gyre

text: wind

text: stress,

text: ρ

text: is

text: the

text: mean

text: ﬂuid

text: density,

text: and

text: H

text: is

text: the

text: mean

text: depth

text: of

text: the

text: ocean

text: basin.

text: In

text: order

text: to

text: obtain

text: a

text: dimensionless

text: of

text: the

text: BVE,

text: we

text: use

text: the

text: following

text: deﬁnitions:

text: x

text: y

text: t

text: ω

text: ψ

text: x˜

text: y˜

text: t˜=

text: ω˜

text: ψ˜

text: L

text: L

text: L/V

text: V/L

text: V

text: L

text: where

text: the

text: tilde

text: denotes

text: the

text: corresponding

text: nondimensional

text: variables.

text: In

text: the

text: nondimensionalization,

text: L

text: represents

text: the

text: characteristic

text: horizontal

text: length

text: scale

text: (in

text: our

text: study

text: L

text: is

text: the

text: basin

text: dimension

text: in

text: the

text: x

text: direction),

text: and

text: V

text: is

text: the

text: characteristic

text: velocity

text: scale.

text: The

text: Sverdrup

text: velocity

text: scale

text: used

text: for

text: nondimen-

text: sionalization

text: can

text: be

text: written

text: in

text: the

text: following

text: form

text: τ

text: π

text: V

text: ρH

text: βL

text: Finally,

text: the

text: governing

text: equations

text: for

text: two-dimensional

text: incompressible

text: barotropic

text: quasigeostrophic

text: ﬂows

text: can

text: be

text: written

text: in

text: dimensionless

text: form

text: in

text: beta-plane

text: as

text: the

text: dimensionless

text: BVE

text: ∂ω

text: ∂ψ

text: J(ω,

text: ψ)

text: 2ω

text: sin(πy),

text: ∂t

text: Ro

text: ∂x

text: Re

text: Ro

text: where

text: we

text: omit

text: the

text: tilde

text: over

text: the

text: variables

text: for

text: clarity

text: purposes.

text: Due

text: to

text: the

text: nondimensionalization

text: given

text: by

text: Eq.

text: the

text: elliptic

text: subproblem

text: given

text: in

text: Eq.

text: remains

text: the

text: same.

text: In

text: the

text: dimensionless

text: form

text: given

text: in

text: Eq,

text: there

text: are

text: only

text: two

text: nondimensional

text: parameters,

text: Reynolds

text: and

text: Rossby

text: numbers,

text: which

text: are

text: related

text: to

text: the

text: physical

text: parameters

text: in

text: the

text: following

text: way:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Word-length entropies and correlations of natural language written texts ∗ Maria Kalimeri 1, Vassilios Constantoudis2, Constantinos Papadimitriou3,4, Konstantinos Karamanos4, Fotis K. Diakonos4, and Harris Papageorgiou5 1Department of Mathematics, National Technical University of Athens, Greece 2Department of Microelectronics, NCSR Demokritos, Aghia Paraskevi, Greece 3IAASARS, National Observatory of Athens, Penteli, Greece 4Department of Physics, University of Athens, Greece 5Institute for Language and Speech Processing, Athena R.C., Greece Abstract We study the frequency distributions and correlations of the word lengths of ten Euro- pean languages. Our ﬁndings indicate that a) the word-length distribution of short words quantiﬁed by the mean value and the entropy distinguishes the Uralic (Finnish) corpus from the others, b) the tails at long words, manifested in the high-order moments of the distributions, diﬀerentiate the Germanic languages (except for English) from the Romanic languages and Greek and c) the correlations between nearby word lengths measured by the comparison of the real entropies with those of the shuﬄed texts are found to be smaller in the case of Germanic and Finnish languages. 1 Introduction In quantitative linguistics, the word length has been considered from the very beginning a key feature whose systematic study can reveal important aspects of language structure, diﬀeren- tiations and text typology. Since 1851, when August de Morgan proposed the study of word lengths as a hallmark of the text style and a possible factor in determining authorship, a great amount of relevant work has been undertaken and published (for a nice review see [1]). The principal aim of these studies has been to introduce and validate theoretical models providing a suﬃcient description of the frequency distribution of the word lengths of various samples (or- dinary or frequency dictionaries, texts of diﬀerent types). These models can then be used for revealing inter-language or intra-language trends and aﬃnities [2, 3, 4, 5, 6, 7, 8, 9]. During the last two decades, word-length representations of written texts have also been in- vestigated in the context of recent advances in time-series analysis and the theory of complex systems. The relevant few studies are diﬀerentiated from the previous linguistic ones in two ways. The ﬁrst is the unit of word-length measurement. Contrary to the main trend in quan- titative linguistics of measuring the word syllables, these studies count the number of word letters (graphemes). Alternatively, the recorded variable in the position of a word can be the rank according to its frequency of appearance [10, 11, 12, 13, 14, 15] or the sum of the Uni- code values of the letters of a word [16]. Secondly, the studies of this category raise the issue ∗ corresponding author, now at Laboratoire de Biochimie Th´eorique, IBPC, CNRS, UPR9080, Univ. Paris Diderot, Sorbonne Paris Cit´e, France, e-mail: maria.kalimeri@ibpc.fr 1 ##LTLine##

text: Word-length

label: title

text: entropies

text: and

text: correlations

text: of

text: natural

text: language

text: written

text: texts

text: Maria

text: Kalimeri

text: Vassilios

text: Constantinos

text: Konstantinos

text: Fotis

text: K.

text: and

text: Harris

text: of

text: Mathematics,

text: National

text: Technical

text: University

text: of

text: Athens,

text: Greece

text: of

text: Microelectronics,

text: NCSR

text: Demokritos,

text: Aghia

text: Paraskevi,

text: Greece

text: National

text: Observatory

text: of

text: Athens,

text: Penteli,

text: Greece

text: of

text: Physics,

text: University

text: of

text: Athens,

text: Greece

text: for

text: Language

text: and

text: Speech

text: Processing,

text: Athena

text: R.C.,

text: Greece

text: Abstract

text: We

label: abstract

text: study

text: the

text: frequency

text: distributions

text: and

text: correlations

text: of

text: the

text: word

text: lengths

text: of

text: ten

text: Euro-

text: pean

text: languages.

text: Our

text: ﬁndings

text: indicate

text: that

text: a)

text: the

text: word-length

text: distribution

text: of

text: short

text: words

text: quantiﬁed

text: by

text: the

text: mean

text: value

text: and

text: the

text: entropy

text: distinguishes

text: the

text: Uralic

text: (Finnish)

text: corpus

text: from

text: the

text: others,

text: b)

text: the

text: tails

text: at

text: long

text: words,

text: manifested

text: in

text: the

text: high-order

text: moments

text: of

text: the

text: distributions,

text: diﬀerentiate

text: the

text: Germanic

text: languages

text: (except

text: for

text: English)

text: from

text: the

text: Romanic

text: languages

text: and

text: Greek

text: and

text: c)

text: the

text: correlations

text: between

text: nearby

text: word

text: lengths

text: measured

text: by

text: the

text: comparison

text: of

text: the

text: real

text: entropies

text: with

text: those

text: of

text: the

text: shuﬄed

text: texts

text: are

text: found

text: to

text: be

text: smaller

text: in

text: the

text: case

text: of

text: Germanic

text: and

text: Finnish

text: languages.

text: Introduction

text: In

text: quantitative

text: linguistics,

text: the

text: word

text: length

text: has

text: been

text: considered

text: from

text: the

text: very

text: beginning

text: a

text: key

text: feature

text: whose

text: systematic

text: study

text: can

text: reveal

text: important

text: aspects

text: of

text: language

text: structure,

text: diﬀeren-

text: tiations

text: and

text: text

text: typology.

text: Since

text: when

text: August

text: de

text: Morgan

text: proposed

text: the

text: study

text: of

text: word

text: lengths

text: as

text: a

text: hallmark

text: of

text: the

text: text

text: style

text: and

text: a

text: possible

text: factor

text: in

text: determining

text: authorship,

text: a

text: great

text: amount

text: of

text: relevant

text: work

text: has

text: been

text: undertaken

text: and

text: published

text: (for

text: a

text: nice

text: review

text: see

text: The

text: principal

text: aim

text: of

text: these

text: studies

text: has

text: been

text: to

text: introduce

text: and

text: validate

text: theoretical

text: models

text: providing

text: a

text: suﬃcient

text: description

text: of

text: the

text: frequency

text: distribution

text: of

text: the

text: word

text: lengths

text: of

text: various

text: samples

text: (or-

text: dinary

text: or

text: frequency

text: dictionaries,

text: texts

text: of

text: diﬀerent

text: types).

text: These

text: models

text: can

text: then

text: be

text: used

text: for

text: revealing

text: inter-language

text: or

text: intra-language

text: trends

text: and

text: aﬃnities

text: During

text: the

text: last

text: two

text: decades,

text: word-length

text: representations

text: of

text: written

text: texts

text: have

text: also

text: been

text: in-

text: vestigated

text: in

text: the

text: context

text: of

text: recent

text: advances

text: in

text: time-series

text: analysis

text: and

text: the

text: theory

text: of

text: complex

text: systems.

text: The

text: relevant

text: few

text: studies

text: are

text: diﬀerentiated

text: from

text: the

text: previous

text: linguistic

text: ones

text: in

text: two

text: ways.

text: The

text: ﬁrst

text: is

text: the

text: unit

text: of

text: word-length

text: measurement.

text: Contrary

text: to

text: the

text: main

text: trend

text: in

text: quan-

text: titative

text: linguistics

text: of

text: measuring

text: the

text: word

text: syllables,

text: these

text: studies

text: count

text: the

text: number

text: of

text: word

text: letters

text: (graphemes).

text: Alternatively,

text: the

text: recorded

text: variable

text: in

text: the

text: position

text: of

text: a

text: word

text: can

text: be

text: the

text: rank

text: according

text: to

text: its

text: frequency

text: of

text: appearance

text: or

text: the

text: sum

text: of

text: the

text: Uni-

text: code

text: values

text: of

text: the

text: letters

text: of

text: a

text: word

text: Secondly,

text: the

text: studies

text: of

text: this

text: category

text: raise

text: the

text: issue

text: corresponding

text: author,

text: now

text: at

text: Laboratoire

text: de

text: Biochimie

text: Th´eorique,

text: IBPC,

text: CNRS,

text: Univ.

text: Paris

text: Diderot,

text: Sorbonne

text: Paris

text: Cit´e,

text: France,

text: e-mail:

text: maria.kalimeri@ibpc.fr

text: ##LTLine##


text: [15] M. Ausloos, “Generalized Hurst exponent and multifractal function of original and trans- lated texts mapped into frequency and length time series,” Phys. Rev. E, vol. 86, p. 031108, 2012. [16] G. S¸ahin, M. Erentu¨rk, and A. Hacinliyan, “Detrended ﬂuctuation analysis in natural languages using non-corpus parametrization,” Chaos, Solitons and Fractals, vol. 41, no. 1, pp. 198–205, 2009. [17] P. Koehn, “Europarl: A Parallel Corpus for Statistical Machine Translation,” in Conference Proceedings: The tenth Machine Translation Summit, (Phuket, Thailand), pp. 79–86, 2005. [18] M. Kalimeri, V. Constantoudis, C. Papadimitriou, K. Karamanos, F. Diakonos, and H. Pa- pageorgiou, “Entropy analysis of word-length series of natural language texts: Eﬀects of text language and genre,” International Journal of Bifurcation and Chaos, vol. 22, no. 9, 2012. [19] G. Nicolis and P. Gaspard, “Toward a probabilistic approach to complex systems,” Chaos, Solitons & Fractals, vol. 4, no. 1, pp. 41–57, 1994. [20] K. Karamanos and G. Nicolis, “Symbolic dynamics and entropy analysis of Feigenbaum limit sets,” Chaos, Solitons, & Fractals, vol. 10, no. 7, pp. 1135–1150, 1999. [21] W. Ebeling and G. Nicolis, “Entropy of symbolic sequences: The role of correlations,” EPL (Europhysics Letters), vol. 14, no. 3, p. 191, 1991. [22] J. S. Nicolis, “Super-selection rules modulating complexity: an overview,” Chaos, Solitons & Fractals, vol. 24, no. 5, pp. 1159–1163, 2005. [23] J. S. Nicolis, “The role of chaos in cognition and music - super selection rules moderating complexity - a research program,” Chaos, Solitons & Fractals, vol. 33, no. 4, pp. 1093–1094, 2007. [24] J. Borwein and K. Karamanos, “Algebraic dynamics of certain gamma function values,” in Generalized Convexity, Generalized Monotonicity and Applications (A. Eberhard, N. Had- jisavvas, and D. Luc, eds.), vol. 77 of Nonconvex Optimization and Its Applications, pp. 3– 21, Springer US, 2005. [25] J. M. Borwein and D. H. Bailey, Mathematics by experiment. A K Peters Ltd., Second ed., 2008. [26] M. A. Montemurro, “Quantifying the information in the long-range order of words: Semantic structures and universal linguistic constraints,” Cortex, 2013, http://dx.doi.org/10.1016/j.cortex.2013.08.008. [27] M. Dunn, S. Greenhill, S. Levinson, and R. Gray, “Evolved structure of language shows lineage-speciﬁc trends in word-order universals,” Nature, vol. 473, no. 7345, pp. 79–82, 2011. 12

text: M.

text: Ausloos,

text: “Generalized

text: Hurst

text: exponent

text: and

text: multifractal

text: function

text: of

text: original

text: and

text: trans-

text: lated

text: texts

text: mapped

text: into

text: frequency

text: and

text: length

text: time

text: series,”

text: Phys.

text: Rev.

text: E,

text: vol.

text: p.

text: G.

text: S¸ahin,

text: M.

text: Erentu¨rk,

text: and

text: A.

text: Hacinliyan,

text: “Detrended

text: ﬂuctuation

text: analysis

text: in

text: natural

text: languages

text: using

text: non-corpus

text: parametrization,”

text: Chaos,

text: Solitons

text: and

text: Fractals,

text: vol.

text: no.

text: pp.

text: P.

text: Koehn,

text: “Europarl:

text: A

text: Parallel

text: Corpus

text: for

text: Statistical

text: Machine

text: Translation,”

text: in

text: Conference

text: Proceedings:

text: The

text: tenth

text: Machine

text: Translation

text: Summit,

text: (Phuket,

text: Thailand),

text: pp.

text: M.

text: Kalimeri,

text: V.

text: Constantoudis,

text: C.

text: Papadimitriou,

text: K.

text: Karamanos,

text: F.

text: Diakonos,

text: and

text: H.

text: Pa-

text: pageorgiou,

text: “Entropy

text: analysis

text: of

text: word-length

text: series

text: of

text: natural

text: language

text: texts:

text: Eﬀects

text: of

text: text

text: language

text: and

text: genre,”

text: International

text: Journal

text: of

text: Bifurcation

text: and

text: Chaos,

text: vol.

text: no.

text: G.

text: Nicolis

text: and

text: P.

text: Gaspard,

text: “Toward

text: a

text: probabilistic

text: approach

text: to

text: complex

text: systems,”

text: Chaos,

text: Solitons

text: Fractals,

text: vol.

text: no.

text: pp.

text: K.

text: Karamanos

text: and

text: G.

text: Nicolis,

text: “Symbolic

text: dynamics

text: and

text: entropy

text: analysis

text: of

text: Feigenbaum

text: limit

text: sets,”

text: Chaos,

text: Solitons,

text: Fractals,

text: vol.

text: no.

text: pp.

text: W.

text: Ebeling

text: and

text: G.

text: Nicolis,

text: “Entropy

text: of

text: symbolic

text: sequences:

text: The

text: role

text: of

text: correlations,”

text: EPL

text: (Europhysics

text: Letters),

text: vol.

text: no.

text: p.

text: J.

text: S.

text: Nicolis,

text: “Super-selection

text: rules

text: modulating

text: complexity:

text: an

text: overview,”

text: Chaos,

text: Solitons

text: Fractals,

text: vol.

text: no.

text: pp.

text: J.

text: S.

text: Nicolis,

text: “The

text: role

text: of

text: chaos

text: in

text: cognition

text: and

text: music

text: super

text: selection

text: rules

text: moderating

text: complexity

text: a

text: research

text: program,”

text: Chaos,

text: Solitons

text: Fractals,

text: vol.

text: no.

text: pp.

text: J.

text: Borwein

text: and

text: K.

text: Karamanos,

text: “Algebraic

text: dynamics

text: of

text: certain

text: gamma

text: function

text: values,”

text: in

text: Generalized

text: Convexity,

text: Generalized

text: Monotonicity

text: and

text: Applications

text: (A.

text: Eberhard,

text: N.

text: Had-

text: jisavvas,

text: and

text: D.

text: Luc,

text: eds.),

text: vol.

text: of

text: Nonconvex

text: Optimization

text: and

text: Its

text: Applications,

text: pp.

text: 3–

text: Springer

text: US,

text: J.

text: M.

text: Borwein

text: and

text: D.

text: H.

text: Bailey,

text: Mathematics

text: by

text: experiment.

text: A

text: K

text: Peters

text: Ltd.,

text: Second

text: ed.,

text: M.

text: A.

text: Montemurro,

text: “Quantifying

text: the

text: information

text: in

text: the

text: long-range

text: order

text: of

text: words:

text: Semantic

text: structures

text: and

text: universal

text: linguistic

text: constraints,”

text: Cortex,

text: M.

text: Dunn,

text: S.

text: Greenhill,

text: S.

text: Levinson,

text: and

text: R.

text: Gray,

text: “Evolved

text: structure

text: of

text: language

text: shows

text: lineage-speciﬁc

text: trends

text: in

text: word-order

text: universals,”

text: Nature,

text: vol.

text: no.

text: pp.


text: A B 2 2 1 1 0. 0. Φ2 Φ3 − − Φ2, shuffled 0.08 Φ3, shuffled 0.08 = = C2 C3 4 4 0 0 0. 0. 0 0 0 0 0. 0. fi de sv nl en it fr es pt el fi de sv nl en it fr es pt el Figure 7: The diﬀerences C and C of the entropies of the source corpora, Φ and Φ , from the 2 3 2 3 respective entropies of the shuﬄed corpora Φ and Φ for all analyzed languages. 2,shuffled 3,shuffled C and C quantify the short-range correlations between nearby word lengths. Notice the smaller 2 3 C and C values (weaker calculations) of the Germanic and Finnish languages with respect to 2 3 the Romanian, Greek and English languages. word lengths. In particular we analyze the word length representation of a large parallel Eu- roparliament corpus translated in 10 diﬀerent European languages, belonging to the Romanic (French, Italian, Spanish, Portuguese), Germanic (English, Dutch, German, Swedish), Uralic (Finnish) and Greek languages. We ﬁnd that, the Uralic (Finnish) corpus can be distinguished on the bases of short and more frequent words which dominate the mean word length and the values of the block entropies. In contrast to that, due to the large and more rare word lengths, the family of Germanic languages, with the notable exception of English, stand out when we focus on higher order moments of the distributions, namely standard deviation, skewness and kurtosis. Finally, the short-range word-length correlations, measured by the diﬀerence of the actual block entropies from those of the shuﬄed versions of the texts, are found to be smaller for both Germanic and Finnish languages. Over all we see that, depending on the metric, the word-length representation is capable not only to distinguish among language families but also to detect deviations originating in cultural inﬂuences, such as the impact of Romanic and Greek languages on the English lexicon. On the contrary, a diﬀerent symbolic representation such as the commonly used frequency-rank series, might fail to produce as fruitful results for small corpora in combination with either distribution moments (due to the very long tails and the power law nature of the distributions) or bigram and trigram entropies (due to the huge number of possible bigram and trigram realizations). Future work may be oriented towards two directions. In the ﬁrst, we can elaborate more on the found diﬀerences between languages and investigate their contribution to the problem of auto- matic language identiﬁcation. In the second direction, one can focus on the issue of word-length correlations at short (intra-sentence) and long scales via the calculation of the relative entropy and correlation metric C for n > 3 to enable a more profound comparison with the ﬁndings n presented by Montemurro and Zanette in [12, 26]. Acknowledgements 10 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A

font: default

text: B

text: Φ2

text: Φ3

text: shuffled

text: shuffled

text: fi

text: de

text: sv

text: nl

text: en

text: it

text: fr

text: es

text: pt

text: el

text: fi

text: de

text: sv

text: nl

text: en

text: it

text: fr

text: es

text: pt

text: el

text: Figure

text: The

text: diﬀerences

text: C

text: and

text: C

text: of

text: the

text: entropies

text: of

text: the

text: source

text: corpora,

text: Φ

text: and

text: Φ

text: from

text: the

text: respective

text: entropies

text: of

text: the

text: shuﬄed

text: corpora

text: Φ

text: and

text: Φ

text: for

text: all

text: analyzed

text: languages.

text: C

text: and

text: C

text: quantify

text: the

text: short-range

text: correlations

text: between

text: nearby

text: word

text: lengths.

text: Notice

text: the

text: smaller

text: C

text: and

text: C

text: values

text: (weaker

text: calculations)

text: of

text: the

text: Germanic

text: and

text: Finnish

text: languages

text: with

text: respect

text: to

text: the

text: Romanian,

text: Greek

text: and

text: English

text: languages.

text: word

text: lengths.

text: In

text: particular

text: we

text: analyze

text: the

text: word

text: length

text: representation

text: of

text: a

text: large

text: parallel

text: Eu-

text: roparliament

text: corpus

text: translated

text: in

text: diﬀerent

text: European

text: languages,

text: belonging

text: to

text: the

text: Romanic

text: (French,

text: Italian,

text: Spanish,

text: Portuguese),

text: Germanic

text: (English,

text: Dutch,

text: German,

text: Swedish),

text: Uralic

text: (Finnish)

text: and

text: Greek

text: languages.

text: We

text: ﬁnd

text: that,

text: the

text: Uralic

text: (Finnish)

text: corpus

text: can

text: be

text: distinguished

text: on

text: the

text: bases

text: of

text: short

text: and

text: more

text: frequent

text: words

text: which

text: dominate

text: the

text: mean

text: word

text: length

text: and

text: the

text: values

text: of

text: the

text: block

text: entropies.

text: In

text: contrast

text: to

text: that,

text: due

text: to

text: the

text: large

text: and

text: more

text: rare

text: word

text: lengths,

text: the

text: family

text: of

text: Germanic

text: languages,

text: with

text: the

text: notable

text: exception

text: of

text: English,

text: stand

text: out

text: when

text: we

text: focus

text: on

text: higher

text: order

text: moments

text: of

text: the

text: distributions,

text: namely

text: standard

text: deviation,

text: skewness

text: and

text: kurtosis.

text: Finally,

text: the

text: short-range

text: word-length

text: correlations,

text: measured

text: by

text: the

text: diﬀerence

text: of

text: the

text: actual

text: block

text: entropies

text: from

text: those

text: of

text: the

text: shuﬄed

text: versions

text: of

text: the

text: texts,

text: are

text: found

text: to

text: be

text: smaller

text: for

text: both

text: Germanic

text: and

text: Finnish

text: languages.

text: Over

text: all

text: we

text: see

text: that,

text: depending

text: on

text: the

text: metric,

text: the

text: word-length

text: representation

text: is

text: capable

text: not

text: only

text: to

text: distinguish

text: among

text: language

text: families

text: but

text: also

text: to

text: detect

text: deviations

text: originating

text: in

text: cultural

text: inﬂuences,

text: such

text: as

text: the

text: impact

text: of

text: Romanic

text: and

text: Greek

text: languages

text: on

text: the

text: English

text: lexicon.

text: On

text: the

text: contrary,

text: a

text: diﬀerent

text: symbolic

text: representation

text: such

text: as

text: the

text: commonly

text: used

text: frequency-rank

text: series,

text: might

text: fail

text: to

text: produce

text: as

text: fruitful

text: results

text: for

text: small

text: corpora

text: in

text: combination

text: with

text: either

text: distribution

text: moments

text: (due

text: to

text: the

text: very

text: long

text: tails

text: and

text: the

text: power

text: law

text: nature

text: of

text: the

text: distributions)

text: or

text: bigram

text: and

text: trigram

text: entropies

text: (due

text: to

text: the

text: huge

text: number

text: of

text: possible

text: bigram

text: and

text: trigram

text: realizations).

text: Future

text: work

text: may

text: be

text: oriented

text: towards

text: two

text: directions.

text: In

text: the

text: ﬁrst,

text: we

text: can

text: elaborate

text: more

text: on

text: the

text: found

text: diﬀerences

text: between

text: languages

text: and

text: investigate

text: their

text: contribution

text: to

text: the

text: problem

text: of

text: auto-

text: matic

text: language

text: identiﬁcation.

text: In

text: the

text: second

text: direction,

text: one

text: can

text: focus

text: on

text: the

text: issue

text: of

text: word-length

text: correlations

text: at

text: short

text: (intra-sentence)

text: and

text: long

text: scales

text: via

text: the

text: calculation

text: of

text: the

text: relative

text: entropy

text: and

text: correlation

text: metric

text: C

text: for

text: n

text: to

text: enable

text: a

text: more

text: profound

text: comparison

text: with

text: the

text: ﬁndings

text: n

text: presented

text: by

text: Montemurro

text: and

text: Zanette

text: in

text: Acknowledgements

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: since 432, 431, 421, 321, 521, and 621 are subsequences in 435621 having the 321 pattern. A permutation σ = σ . . . σ can be represented as a function σ that maps i to σ(i) = σ . The 1 N { } i graph of this function is the set of N points (i, σ ) : i = 1 . . . N (see Figure 1). Points of the i form (i, σ ) = (i, i) are said to be on the diagonal of the graph of σ (these correspond to ﬁxed i points of the permutation). 6 5 4 3 2 1 0 1 2 3 4 5 6 ∈ (cid:55)→ Figure 1: σ = 435621 S viewed as a function i σ . This is a 312-avoiding permutation. 6 i The study of pattern-avoiding permutations often reveals connections to other combinatorial objects. For example in [3] it is shown that there is a bijection between 1342-avoiding permu- tations and plane forests of β(0, 1)-trees, as well as with ordered collections of rooted bicubic planar maps. Among other well studied connections of permutations excluding or including certain pat- terns in the literature are Kazhdan-Lusztig polynomials, singularities of Schubert varieties, Chebyshev polynomials, rook polynomials for Ferrers boards. In a recent book [7] Kitaev goes through a vast amount of literature to point out the connections of permutations with other mathematical objects. Also, Bouvel and Rossin [5] show how permutation patterns are related to problems in computational biology. One of the initial motivations to study pattern avoiding permutations came from computer science. A basic problem in computer science is sorting n distinct elements in increasing order. Stack sorting is an algorithm that does the sorting operation eﬃciently, although it only works on some permutations. It was observed that a permutation is stack sortable if and only if it avoids the pattern 231. A detailed explanation of the connection can be found in B´ona’s book [4]. An important reference on stack sorting is Knuth’s book [8]. Two recent papers of Madras and Liu [11] and Atapour and Madras [1] present numerical and probabilistic approaches to investigate the shapes of random pattern avoiding permutations, mainly of length three, four and ﬁve. Both papers include Monte Carlo simulations suggesting the limiting distributions of the positions of points of the permutations. For example Atapour and Madras [1] present the result of Monte Carlo simulation (similar to Figure 2 here) which suggests that typical 312-avoiding permutations are accumulated near the diagonal as well as below the diagonal. To generate random 312-avoiding permutations, they run a Markov chain on S (312) which is irreducible, symmetric and aperiodic [11], and hence has the uniform N 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: since

text: and

text: are

text: subsequences

text: in

text: having

text: the

text: pattern.

text: A

text: permutation

text: σ

text: σ

text: σ

text: can

text: be

text: represented

text: as

text: a

text: function

text: σ

text: that

text: maps

text: i

text: to

text: σ(i)

text: σ

text: The

text: N

text: i

text: graph

text: of

text: this

text: function

text: is

text: the

text: set

text: of

text: N

text: points

text: (i,

text: σ

text: i

text: N

text: (see

text: Figure

text: Points

text: of

text: the

text: i

text: form

text: (i,

text: σ

text: (i,

text: i)

text: are

text: said

text: to

text: be

text: on

text: the

text: diagonal

text: of

text: the

text: graph

text: of

text: σ

text: (these

text: correspond

text: to

text: ﬁxed

text: i

text: points

text: of

text: the

text: permutation).

text: Figure

text: σ

text: S

text: viewed

text: as

text: a

text: function

text: i

text: σ

text: This

text: is

text: a

text: permutation.

text: i

text: The

text: study

text: of

text: pattern-avoiding

text: permutations

text: often

text: reveals

text: connections

text: to

text: other

text: combinatorial

text: objects.

text: For

text: example

text: in

text: it

text: is

text: shown

text: that

text: there

text: is

text: a

text: bijection

text: between

text: permu-

text: tations

text: and

text: plane

text: forests

text: of

text: as

text: well

text: as

text: with

text: ordered

text: collections

text: of

text: rooted

text: bicubic

text: planar

text: maps.

text: Among

text: other

text: well

text: studied

text: connections

text: of

text: permutations

text: excluding

text: or

text: including

text: certain

text: pat-

text: terns

text: in

text: the

text: literature

text: are

text: Kazhdan-Lusztig

text: polynomials,

text: singularities

text: of

text: Schubert

text: varieties,

text: Chebyshev

text: polynomials,

text: rook

text: polynomials

text: for

text: Ferrers

text: boards.

text: In

text: a

text: recent

text: book

text: Kitaev

text: goes

text: through

text: a

text: vast

text: amount

text: of

text: literature

text: to

text: point

text: out

text: the

text: connections

text: of

text: permutations

text: with

text: other

text: mathematical

text: objects.

text: Also,

text: Bouvel

text: and

text: Rossin

text: show

text: how

text: permutation

text: patterns

text: are

text: related

text: to

text: problems

text: in

text: computational

text: biology.

text: One

text: of

text: the

text: initial

text: motivations

text: to

text: study

text: pattern

text: avoiding

text: permutations

text: came

text: from

text: computer

text: science.

text: A

text: basic

text: problem

text: in

text: computer

text: science

text: is

text: sorting

text: n

text: distinct

text: elements

text: in

text: increasing

text: order.

text: Stack

text: sorting

text: is

text: an

text: algorithm

text: that

text: does

text: the

text: sorting

text: operation

text: eﬃciently,

text: although

text: it

text: only

text: works

text: on

text: some

text: permutations.

text: It

text: was

text: observed

text: that

text: a

text: permutation

text: is

text: stack

text: sortable

text: if

text: and

text: only

text: if

text: it

text: avoids

text: the

text: pattern

text: A

text: detailed

text: explanation

text: of

text: the

text: connection

text: can

text: be

text: found

text: in

text: B´ona’s

text: book

text: An

text: important

text: reference

text: on

text: stack

text: sorting

text: is

text: Knuth’s

text: book

text: Two

text: recent

text: papers

text: of

text: Madras

text: and

text: Liu

text: and

text: Atapour

text: and

text: Madras

text: present

text: numerical

text: and

text: probabilistic

text: approaches

text: to

text: investigate

text: the

text: shapes

text: of

text: random

text: pattern

text: avoiding

text: permutations,

text: mainly

text: of

text: length

text: three,

text: four

text: and

text: ﬁve.

text: Both

text: papers

text: include

text: Monte

text: Carlo

text: simulations

text: suggesting

text: the

text: limiting

text: distributions

text: of

text: the

text: positions

text: of

text: points

text: of

text: the

text: permutations.

text: For

text: example

text: Atapour

text: and

text: Madras

text: present

text: the

text: result

text: of

text: Monte

text: Carlo

text: simulation

text: (similar

text: to

text: Figure

text: here)

text: which

text: suggests

text: that

text: typical

text: permutations

text: are

text: accumulated

text: near

text: the

text: diagonal

text: as

text: well

text: as

text: below

text: the

text: diagonal.

text: To

text: generate

text: random

text: permutations,

text: they

text: run

text: a

text: Markov

text: chain

text: on

text: S

text: which

text: is

text: irreducible,

text: symmetric

text: and

text: aperiodic

text: and

text: hence

text: has

text: the

text: uniform

text: N

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: maximum. Hence, using Krattenthaler’s bijection from Section 3.1, these two points correspond − − − − − − − − − to peaks at (j + (i 1), j (i 1)) and (j + i 2(N t i ) 1, j (i 1)) on the Dyck 1 1 1 1 | 2 2 | 1 1 2 2 path associated with σ. We deduce that S∩(N, i , i ) equals the product of the cardinalities 1 2 of the three sets of Dyck segments D , D , D , where (1) (2) (3) • − − D is the set of Dyck segments from (0, 0) to (j + i 2, j i ), (1) 1 1 1 1 • − − − − − − D is the set of Dyck segments from (j + i , j i ) to (j + i 2(N t i ) 2, j i ), (2) 1 1 1 1 2 2 1 1 2 2 and • − − − − − D is the set of Dyck segments from (j +i 2(N t i ), j i ) to (2(i +i +t +t N), 0), (3) 2 2 1 1 2 2 1 2 1 2 − which has the same cardinality as the set of Dyck segments from (0, 0) to (2(i + i + t + t − − − − − − − 1 2 1 2 N) (j2 + i2 2(N t1 (cid:18)i1)), j2 i2(cid:19)) = (i2 + 2t2 j2, j2 i2). (cid:12) (cid:12) Reca(cid:12)lling (cid:12)Lemma 3.3 and Remark 3.4, we obtain − − (cid:18) (cid:19) (cid:18) (cid:19) (cid:12)(cid:12)D (cid:12)(cid:12) = j1 i1 + 1 j1 + −i1 2 , (1) j j 1 1 − 1 − − − − − (cid:18) (cid:19) (cid:12)(cid:12)D (cid:12)(cid:12) = i1 + i2 + j−2 j−1 2−(N −t1 + 1) − i1 + i2 + j2 −j1 −2(N t1 + 1) , (2) j + (i j 1) (N t ) j (N t ) −2 1 1 − 1 2 1 j2 i2 + 1 i2 + 2t2 j(cid:12)2 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) D = (cid:12) . (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (3) t + 1 t 2 2 | | Using the above and S∩(N, i , i ) = D D D in Equation (5), the proof of part (b) 1 2 (1) (2) (3) is now complete. − (cid:12) (cid:12) (cid:0) (cid:1) (cid:0) (cid:1) | (cid:37) | Notice that when j = N t +(cid:12) 1, e(cid:12)ach sum in the formula for S (N) has only one term, 2 1 namely i = j (cid:12)in the o(cid:12) uter sum and i = j in the inner sum. Hence in this case we obtain | | 1 1 | | 2 2 − (cid:12) (cid:12) D = C − , D = C , and D = 0 0 = 1, which yields the expression (1) j1 1 (3) t2 (2) 0 1 (cid:37) − S (N) = C − − C − − C − C when j = N t + 1. N t1 j1 t1 t2 1 j1 1 t2 2 1 5 Asymptotics of Probabilities • The main goal of this section is to prove asymptotic formulas for the probabilities of S (N, i, j), (cid:38) (cid:37) S (N), and S (N), as described in Section 2. The asymptotics are based on well known asymptotics of binomial pr(cid:18)oba(cid:19)bilities, o(cid:114)f which the following is a particularly useful form. Proposition 5.1. ([10], pp. 61–63) We have the relatio(cid:18)n (cid:19) A 2−A = 2 e−(2B2−AA)2 eO A1 +(2BA−3A)4 B πA | −(cid:18) |(cid:19)≤ (cid:114) (cid:18) (cid:18) (cid:19)(cid:19) and hence, if 2B A A3/4, − A 2−A = 2 e−(2B−A)2 1 + O 1 + (2B A)4 . 2A B πA A A3 22 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: maximum.

text: Hence,

text: using

text: Krattenthaler’s

text: bijection

text: from

text: Section

text: these

text: two

text: points

text: correspond

text: to

text: peaks

text: at

text: (j

text: (i

text: j

text: (i

text: and

text: (j

text: i

text: t

text: i

text: j

text: (i

text: on

text: the

text: Dyck

text: path

text: associated

text: with

text: σ.

text: We

text: deduce

text: that

text: S∩(N,

text: i

text: i

text: equals

text: the

text: product

text: of

text: the

text: cardinalities

text: of

text: the

text: three

text: sets

text: of

text: Dyck

text: segments

text: D

text: D

text: D

text: where

text: D

text: is

text: the

text: set

text: of

text: Dyck

text: segments

text: from

text: to

text: (j

text: i

text: j

text: i

text: D

text: is

text: the

text: set

text: of

text: Dyck

text: segments

text: from

text: (j

text: i

text: j

text: i

text: to

text: (j

text: i

text: t

text: i

text: j

text: i

text: and

text: D

text: is

text: the

text: set

text: of

text: Dyck

text: segments

text: from

text: (j

text: +i

text: t

text: i

text: j

text: i

text: to

text: +i

text: +t

text: +t

text: N),

text: which

text: has

text: the

text: same

text: cardinality

text: as

text: the

text: set

text: of

text: Dyck

text: segments

text: from

text: to

text: i

text: t

text: t

text: N)

text: and

text: Remark

text: we

text: obtain

text: j

text: j

text: j

text: (i

text: j

text: (N

text: t

text: j

text: (N

text: t

text: −2

text: D

text: t

text: t

text: Using

text: the

text: above

text: and

text: S∩(N,

text: i

text: i

text: D

text: D

text: D

text: in

text: Equation

text: the

text: proof

text: of

text: part

text: (b)

text: is

text: now

text: complete.

text: Notice

text: that

text: when

text: j

text: N

text: t

text: sum

text: in

text: the

text: formula

text: for

text: S

text: (N)

text: has

text: only

text: one

text: term,

text: namely

text: i

text: j

text: the

text: uter

text: sum

text: and

text: i

text: j

text: in

text: the

text: inner

text: sum.

text: Hence

text: in

text: this

text: case

text: we

text: obtain

text: D

text: C

text: D

text: C

text: and

text: D

text: which

text: yields

text: the

text: expression

text: S

text: (N)

text: C

text: C

text: C

text: C

text: when

text: j

text: N

text: t

text: N

text: Asymptotics

text: of

text: Probabilities

text: The

text: main

text: goal

text: of

text: this

text: section

text: is

text: to

text: prove

text: asymptotic

text: formulas

text: for

text: the

text: probabilities

text: of

text: S

text: (N,

text: i,

text: j),

text: S

text: (N),

text: and

text: S

text: (N),

text: as

text: described

text: in

text: Section

text: The

text: asymptotics

text: are

text: based

text: on

text: well

text: known

text: asymptotics

text: of

text: binomial

text: which

text: the

text: following

text: is

text: a

text: particularly

text: useful

text: form.

text: Proposition

text: pp.

text: We

text: have

text: the

text: A

text: eO

text: B

text: πA

text: and

text: hence,

text: if

text: A

text: A

text: O

text: B

text: πA

text: A

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##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:32)(cid:32) (cid:33) (cid:33) (cid:89) (cid:89) (cid:32)(cid:32) (cid:33) − (cid:33) θN(D, F ) = EN (cid:89) XqN (cid:88)(1(cid:89) XrN) ∈ ∈ q D r F (cid:32) −(cid:33) = E(cid:88)N XqN (cid:89) ( XsN) ∈ ⊂ ∈ q D G F s G (cid:88) − | | = ( 1) G E XN N s ⊂ ∈ ∪ G F s D G − | | ∪ ∅ = ( 1) G θ (D G, ). (18) N ⊂ G F → ∞ From the previous paragraph, we know that the ﬁnal expression converges as N . Hence θ (D, F ) converges. N Having proven the above theorem, we know that ∀ ∈ ∀ ∈ ⊂ θ(D, F ) = P∞(X = 1 q D, and X = 0 r F ) for ﬁnite D, F Q. q r { } Some properties of the limiting collection X follow immediately from Proposition 2.15. − q In particular, P∞(X − = 1) = ρ(i, j) = 1 P∞(X − = 0). More generally, we see from ( i,j) ( i,j) Proposition 2.15(b) that if T is a ﬁnite subset of Q of the form { − (cid:88) (cid:88) } T = ( A , B ) : m = 1, . . . , k where m m m m ∈ N A = a , B = b for m = 1, . . . , k and a , . . . , a , b , . . . , b (19) m l m l (cid:81) 1 k 1 k l=1 l=1 ∈ (cid:45) ∅ (in particular T Seq ), then θ(T, ) = k ρ(a , b ). As we mentioned in section , this m=1 m m is a kind of two-dimensional regenerative property that corresponds to the fact (Theorem 2.19, proven below) that the random set of points q where X is 1 follows the law of a trajectory of q a random walk that can only move up and left—i.e., a two-dimensional analogue of a renewal − − × \ process. Another special case we consider is θ(T, B(T )) where B(T ) = [ A , 1] [1, B ] T ; k k this is the probability that T is exactly the set of locations of all the 1’s in the smallest rectangle containing T and the bottom right corner of Q. Proposition 6.3 below shows that θ(T, B(T )) also has a product form. Notation 6.1. For T of the form (19) let { ∈ Λ (T ) = σ S (312) : σ − = B for m = 1, . . . , k and σ − > B for N ∈ N \ { N Am+1}} m N t+1 k t [1, A ] A , . . . , A . k 1 k 32 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: θN(D,

text: F

text: EN

text: XqN

text: XrN)

text: q

text: D

text: r

text: F

text: XqN

text: XsN)

text: q

text: D

text: G

text: F

text: s

text: G

text: G

text: E

text: XN

text: N

text: s

text: G

text: F

text: s

text: D

text: G

text: G

text: θ

text: (D

text: G,

text: N

text: G

text: F

text: From

text: the

text: previous

text: paragraph,

text: we

text: know

text: that

text: the

text: ﬁnal

text: expression

text: converges

text: as

text: N

text: Hence

text: θ

text: (D,

text: F

text: converges.

text: N

text: Having

text: proven

text: the

text: above

text: theorem,

text: we

text: know

text: that

text: θ(D,

text: F

text: P∞(X

text: q

text: D,

text: and

text: X

text: r

text: F

text: for

text: ﬁnite

text: D,

text: F

text: Q.

text: q

text: r

text: Some

text: properties

text: of

text: the

text: limiting

text: collection

text: X

text: follow

text: immediately

text: from

text: Proposition

text: q

text: In

text: particular,

text: P∞(X

text: ρ(i,

text: j)

text: P∞(X

text: More

text: generally,

text: we

text: see

text: from

text: i,j)

text: i,j)

text: Proposition

text: that

text: if

text: T

text: is

text: a

text: ﬁnite

text: subset

text: of

text: Q

text: of

text: the

text: form

text: T

text: A

text: B

text: m

text: k

text: where

text: m

text: m

text: m

text: m

text: N

text: A

text: a

text: B

text: b

text: for

text: m

text: k

text: and

text: a

text: a

text: b

text: b

text: m

text: l

text: m

text: l

text: k

text: k

text: (in

text: particular

text: T

text: Seq

text: then

text: θ(T,

text: k

text: ρ(a

text: b

text: As

text: we

text: mentioned

text: in

text: section

text: this

text: m

text: m

text: is

text: a

text: kind

text: of

text: two-dimensional

text: regenerative

text: property

text: that

text: corresponds

text: to

text: the

text: fact

text: (Theorem

text: proven

text: below)

text: that

text: the

text: random

text: set

text: of

text: points

text: q

text: where

text: X

text: is

text: follows

text: the

text: law

text: of

text: a

text: trajectory

text: of

text: q

text: a

text: random

text: walk

text: that

text: can

text: only

text: move

text: up

text: and

text: left—i.e.,

text: a

text: two-dimensional

text: analogue

text: of

text: a

text: renewal

text: process.

text: Another

text: special

text: case

text: we

text: consider

text: is

text: θ(T,

text: B(T

text: where

text: B(T

text: A

text: B

text: T

text: k

text: k

text: this

text: is

text: the

text: probability

text: that

text: T

text: is

text: exactly

text: the

text: set

text: of

text: locations

text: of

text: all

text: the

text: in

text: the

text: smallest

text: rectangle

text: containing

text: T

text: and

text: the

text: bottom

text: right

text: corner

text: of

text: Q.

text: Proposition

text: below

text: shows

text: that

text: θ(T,

text: B(T

text: also

text: has

text: a

text: product

text: form.

text: Notation

text: For

text: T

text: of

text: the

text: form

text: let

text: Λ

text: (T

text: σ

text: S

text: σ

text: B

text: for

text: m

text: k

text: and

text: σ

text: B

text: for

text: N

text: N

text: N

text: m

text: N

text: k

text: t

text: A

text: A

text: A

text: k

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:88) (cid:104) (cid:105) where A, B denotes (cid:104) (cid:105) A, B = A B . jk jk j,k H For a BHHB tensor with the generating matrix H, we do the embedding twice. First we embed each Hankel block into a larger anti-circulant block, and then we embed the block Hankel tensor with anti-circulant blocks into C C a BAAB tensor H. Notice that the compressed generating matrix of H is H exactlythe gen(cid:20)eHra×ting m· ·a·tr×ix o(cid:21)f(cid:27) . Hence we have the fast procedure for computing y = x x  2 2 m m    − (cid:124)vec 1 (cid:123)((cid:122)x ) O(cid:125) ··· −  X˜p = (cid:0) np,ONp p O n1+n2+ +nm m+1, p =(cid:1) 2, 3, . . . , m,    (cid:0) (cid:1)  ··· − N1+N2+ +Nm∗ m+1 ∗ · · · ∗ ˜ ˜ ˜ Y = ﬀt2 iﬀt2(H). ﬀt2(X ). . ﬀt2(X ) , − 2 − m ˜ y = vec Y (0 : n 1, 0 : N 1) . 1 1 Sometimes in applications there is no need to do the vectorization in the last line, and we ju(cid:20)st keep it as aHm(cid:21)×(cid:27)atrix ×for lat·e·r· ×use. We also have the fast procedure for computing α = x x x  1 1 2 2 m m  − (cid:124)vec 1 (cid:123)((cid:122)x ) O(cid:125) ··· −  X˜p =(cid:10) np,ONp p O n1+n2+ +nm m+1, p = 2, 3(cid:11), . . . , m, ··· − N1+N2+ +Nm m+1∗ ∗ · · · ∗ ˜ ˜ ˜ α = iﬀt2(H), ﬀt2(X ). ﬀt2(X ). . ﬀt2(X ) . 1 2 m Similarly, we can also derive the fast algorithms for higher-level block Hankel tensor-vector products using the multi-dimensional FFT. 4 Exponential Data Fitting Exponential data ﬁtting is very important in many applications in sci- entiﬁc computing and engineering, which represents the signals as a sum of exponentially damped sinusoids. The computations and applications of expo- nential data ﬁtting are generally studied, and the reader is interested in these topics can refer to [20]. Furthermore, Papy et al. introduced a higher-order tensor approach into exponential data ﬁtting in [18, 19] by connecting it with the Vandermonde decomposition of a Hankel tensor. And they showed that the tensor approach can do better than the classical matrix approach. 4.1 Hankel Tensor Approach 11

text: where

text: A,

text: B

text: denotes

text: A,

text: B

text: A

text: B

text: jk

text: jk

text: j,k

text: H

text: For

text: a

text: BHHB

text: tensor

text: with

text: the

text: generating

text: matrix

text: H,

text: we

text: do

text: the

text: embedding

text: twice.

text: First

text: we

text: embed

text: each

text: Hankel

text: block

text: into

text: a

text: larger

text: anti-circulant

text: block,

text: and

text: then

text: we

text: embed

text: the

text: block

text: Hankel

text: tensor

text: with

text: anti-circulant

text: blocks

text: into

text: C

text: C

text: a

text: BAAB

text: tensor

text: H.

text: Notice

text: that

text: the

text: compressed

text: generating

text: matrix

text: of

text: H

text: is

text: H

text: exactlythe

text: m·

text: ·a·tr×ix

text: Hence

text: we

text: have

text: the

text: fast

text: procedure

text: for

text: computing

text: y

text: x

text: x

text: m

text: m

text: X˜p

text: np,ONp

text: p

text: O

text: +nm

text: p

text: m,

text: +Nm∗

text: Y

text: m

text: y

text: vec

text: Y

text: n

text: N

text: Sometimes

text: in

text: applications

text: there

text: is

text: no

text: need

text: to

text: do

text: the

text: vectorization

text: in

text: the

text: last

text: line,

text: and

text: we

text: keep

text: it

text: as

text: ×for

text: lat·e·r·

text: ×use.

text: We

text: also

text: have

text: the

text: fast

text: procedure

text: for

text: computing

text: α

text: x

text: x

text: x

text: m

text: m

text: X˜p

text: np,ONp

text: p

text: O

text: +nm

text: p

text: m,

text: +Nm

text: α

text: m

text: Similarly,

text: we

text: can

text: also

text: derive

text: the

text: fast

text: algorithms

text: for

text: higher-level

text: block

text: Hankel

text: tensor-vector

text: products

text: using

text: the

text: multi-dimensional

text: FFT.

text: Exponential

text: Data

text: Fitting

text: Exponential

text: data

text: ﬁtting

text: is

text: very

text: important

text: in

text: many

text: applications

text: in

text: sci-

text: entiﬁc

text: computing

text: and

text: engineering,

text: which

text: represents

text: the

text: signals

text: as

text: a

text: sum

text: of

text: exponentially

text: damped

text: sinusoids.

text: The

text: computations

text: and

text: applications

text: of

text: expo-

text: nential

text: data

text: ﬁtting

text: are

text: generally

text: studied,

text: and

text: the

text: reader

text: is

text: interested

text: in

text: these

text: topics

text: can

text: refer

text: to

text: Furthermore,

text: Papy

text: et

text: al.

text: introduced

text: a

text: higher-order

text: tensor

text: approach

text: into

text: exponential

text: data

text: ﬁtting

text: in

text: by

text: connecting

text: it

text: with

text: the

text: Vandermonde

text: decomposition

text: of

text: a

text: Hankel

text: tensor.

text: And

text: they

text: showed

text: that

text: the

text: tensor

text: approach

text: can

text: do

text: better

text: than

text: the

text: classical

text: matrix

text: approach.

text: Hankel

text: Tensor

text: Approach