text: [12] Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Maximum throughput of multiple access channels in adversarial environments. Distributed Computing, 22(2):93–116, 2009. [13] Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Adversarial queuing on the multiple access channel. ACM Transactions on Algorithms, 8(1):5:1–5:31, 2012. [14] Robert G. Gallager. A perspective on multiaccess channels. IEEE Transactions on Information Theory, 31(2):124–142, 1985. [15] David Gamarnik. Stability of adaptive and nonadaptive packet routing policies in adversarial queueing networks. SIAM Journal on Computing, 32(2):371–385, 2003. [16] Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson. A bound on the capacity of backoﬀ and acknowledgment-based protocols. SIAM Journal on Computing, 33(2):313–331, 2004. [17] Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, and Aravind Srinivasan. Con- tention resolution with constant expected delay. Journal of the ACM, 47(6):1048–1096, 2000. [18] Johan H˚astad, Frank Thompson Leighton, and Brian Rogoﬀ. Analysis of backoﬀ protocols for multiple access channels. SIAM Journal on Computing, 25(4):740–774, 1996. [19] Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris E. Nikoletseas, and Paul G. Spirakis. The impact of network structure on the stability of greedy protocols. Theory of Computing Systems, 38(4):425–460, 2005. [20] Zvi Lotker, Boaz Patt-Shamir, and Adi Ros´en. New stability results for adversarial queuing. SIAM Journal on Computing, 33(2):286–303, 2004. [21] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996. [22] Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395–404, 1976. [23] Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press, second edition, 2017. [24] Prabhakar Raghavan and Eli Upfal. Stochastic contention resolution with short delays. SIAM Journal on Computing, 28(2):709–719, 1998. [25] Paulo Ribenboim. The New Book of Prime Number Records. Springer-Verlag, third edition, 1996. [26] Adi Ros´en. A note on models for non-probabilistic analysis of packet switching networks. Information Processing Letters, 84(5):237–240, 2002. 36

text: Bogdan

text: S.

text: Chlebus,

text: Dariusz

text: R.

text: Kowalski,

text: and

text: Mariusz

text: A.

text: Rokicki.

text: Maximum

text: throughput

text: of

text: multiple

text: access

text: channels

text: in

text: adversarial

text: environments.

text: Distributed

text: Computing,

text: Bogdan

text: S.

text: Chlebus,

text: Dariusz

text: R.

text: Kowalski,

text: and

text: Mariusz

text: A.

text: Rokicki.

text: Adversarial

text: queuing

text: on

text: the

text: multiple

text: access

text: channel.

text: ACM

text: Transactions

text: on

text: Algorithms,

text: Robert

text: G.

text: Gallager.

text: A

text: perspective

text: on

text: multiaccess

text: channels.

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: David

text: Gamarnik.

text: Stability

text: of

text: adaptive

text: and

text: nonadaptive

text: packet

text: routing

text: policies

text: in

text: adversarial

text: queueing

text: networks.

text: SIAM

text: Journal

text: on

text: Computing,

text: Leslie

text: Ann

text: Goldberg,

text: Mark

text: Jerrum,

text: Sampath

text: Kannan,

text: and

text: Mike

text: Paterson.

text: A

text: bound

text: on

text: the

text: capacity

text: of

text: backoﬀ

text: and

text: acknowledgment-based

text: protocols.

text: SIAM

text: Journal

text: on

text: Computing,

text: Leslie

text: Ann

text: Goldberg,

text: Philip

text: D.

text: MacKenzie,

text: Mike

text: Paterson,

text: and

text: Aravind

text: Srinivasan.

text: Con-

text: tention

text: resolution

text: with

text: constant

text: expected

text: delay.

text: Journal

text: of

text: the

text: ACM,

text: Johan

text: H˚astad,

text: Frank

text: Thompson

text: Leighton,

text: and

text: Brian

text: Rogoﬀ.

text: Analysis

text: of

text: backoﬀ

text: protocols

text: for

text: multiple

text: access

text: channels.

text: SIAM

text: Journal

text: on

text: Computing,

text: Dimitrios

text: Koukopoulos,

text: Marios

text: Mavronicolas,

text: Sotiris

text: E.

text: Nikoletseas,

text: and

text: Paul

text: G.

text: Spirakis.

text: The

text: impact

text: of

text: network

text: structure

text: on

text: the

text: stability

text: of

text: greedy

text: protocols.

text: Theory

text: of

text: Computing

text: Systems,

text: Zvi

text: Lotker,

text: Boaz

text: Patt-Shamir,

text: and

text: Adi

text: Ros´en.

text: New

text: stability

text: results

text: for

text: adversarial

text: queuing.

text: SIAM

text: Journal

text: on

text: Computing,

text: Nancy

text: A.

text: Lynch.

text: Distributed

text: Algorithms.

text: Morgan

text: Kaufmann

text: Publishers,

text: Robert

text: M.

text: Metcalfe

text: and

text: David

text: R.

text: Boggs.

text: Ethernet:

text: Distributed

text: packet

text: switching

text: for

text: local

text: computer

text: networks.

text: Communications

text: of

text: the

text: ACM,

text: Michael

text: Mitzenmacher

text: and

text: Eli

text: Upfal.

text: Probability

text: and

text: Computing.

text: Cambridge

text: University

text: Press,

text: second

text: edition,

text: Prabhakar

text: Raghavan

text: and

text: Eli

text: Upfal.

text: Stochastic

text: contention

text: resolution

text: with

text: short

text: delays.

text: SIAM

text: Journal

text: on

text: Computing,

text: Paulo

text: Ribenboim.

text: The

text: New

text: Book

text: of

text: Prime

text: Number

text: Records.

text: Springer-Verlag,

text: third

text: edition,

text: Adi

text: Ros´en.

text: A

text: note

text: on

text: models

text: for

text: non-probabilistic

text: analysis

text: of

text: packet

text: switching

text: networks.

text: Information

text: Processing

text: Letters,


text: mechanism is available, then stations perceive collisions as silences. Adversaries. We consider the worst-case performance of algorithms that handle traﬃc deter- mined by an adversarial setting. The rate of packet injection of an adversary means an upper bound on the average number of packets injected into all the stations. The maximum number of packets that an adversary may inject into all the stations at a round is called the burstiness. An adversary is deﬁned by these two parameters: injection rate and burstiness. An injection rate can be deﬁned in various ways depending on the class of time segments over which we average. We consider two kinds of adversaries: window adversaries and leaky-bucket ones. In the context of adversarial queuing, window adversaries were ﬁrst used by Borodin, et al. [7] and leaky-bucket adversaries by Andrews, et al. [4]. ≤ We will use the letter ρ to denote injection rate; we require the inequalities 0 < ρ 1 to hold. Let ρ be an injection rate and w a positive integer: the window adversary of type (ρ, w) may inject at most ρw packets in each contiguous segment of w rounds into any set of stations; the number w is called the window size in such a context. Let ρ be an injection rate and b a non-negative integer: the leaky-bucket adversary of type (ρ, b) may inject at most ρt + b packets in every contiguous segment of t > 0 rounds into any set of stations. An adversary is said to be of injection rate ρ when it is either of window type (ρ, w) or of leaky-bucket-type (ρ, b), for some w and b, respectively. The (cid:98) (cid:99) window adversary of type (ρ, w) has burstiness ρw . The leaky-bucket adversary of type (ρ, b) has (cid:98) (cid:99) burstiness ρ + b . Observe that injection rate larger than 1 would allow the adversary to make the number of packets queued at stations grow unbounded, as at most one packet can be heard per round. In this paper, we consider only adversaries of injection rates exactly 1. Such adversaries diﬀer among themselves by their burstiness, which is either the window size w for a window adversary, or the number b+1 for a leaky-bucket adversary. The models of window adversaries and leaky-bucket ones are equivalent for injection rates strictly less than 1, while the leaky-bucket adversary of injection rate 1 can generate sequences of injections not captured by any window adversary of rate 1, as was showed by Ros´en [26]. It follows that a possibility-type of a result for leaky-bucket adversaries holds automatically for window adversaries, while an impossibility result showed for window adversaries holds automatically for leaky-bucket adversaries. Distributed deterministic broadcasting. We consider broadcasting algorithms for a system of stations attached to a multiple access channel. The algorithms are restricted to be both distributed and deterministic. Further requirements for broadcast algorithms may stem from additional as- sumptions about channels. For instance, when a channel is equipped with a collision detection mechanism then algorithms need to be able to react diﬀerently to collisions as opposed to silent rounds. The “slotted” model of full synchrony does not impose any restrictions on speciﬁcations of algorithms: stations simply act driven by their local clocks. On the other hand, the quality of broadcasting, for instance as measured by the maximum throughput achievable for a given number of stations, may be aﬀected by the level of synchrony among the clocks at stations. Any deﬁnition of algorithms needs to reﬂect general expectations of what algorithms are to accomplish. We simply want algorithms to facilitate hearing packets on a channel, in a distributed and deterministic manner, while packets are injected into stations. There are numerous tacit assumptions in such expectations, let us next discuss the key ones. We want a station to have private memory to store incoming packets while waiting for access 5

text: mechanism

label: paragraph

text: is

text: available,

text: then

text: stations

text: perceive

text: collisions

text: as

text: silences.

text: Adversaries.

text: We

text: consider

text: the

text: worst-case

text: performance

text: of

text: algorithms

text: that

text: handle

text: traﬃc

text: deter-

text: mined

text: by

text: an

text: adversarial

text: setting.

text: The

text: rate

text: of

text: packet

text: injection

text: of

text: an

text: adversary

text: means

text: an

text: upper

text: bound

text: on

text: the

text: average

text: number

text: of

text: packets

text: injected

text: into

text: all

text: the

text: stations.

text: The

text: maximum

text: number

text: of

text: packets

text: that

text: an

text: adversary

text: may

text: inject

text: into

text: all

text: the

text: stations

text: at

text: a

text: round

text: is

text: called

text: the

text: burstiness.

text: An

text: adversary

text: is

text: deﬁned

text: by

text: these

text: two

text: parameters:

text: injection

text: rate

text: and

text: burstiness.

text: An

text: injection

text: rate

text: can

text: be

text: deﬁned

text: in

text: various

text: ways

text: depending

text: on

text: the

text: class

text: of

text: time

text: segments

text: over

text: which

text: we

text: average.

text: We

text: consider

text: two

text: kinds

text: of

text: adversaries:

text: window

text: adversaries

text: and

text: leaky-bucket

text: ones.

text: In

text: the

text: context

text: of

text: adversarial

text: queuing,

text: window

text: adversaries

text: were

text: ﬁrst

text: used

text: by

text: Borodin,

text: et

text: al.

text: and

text: leaky-bucket

text: adversaries

text: by

text: Andrews,

text: et

text: al.

text: We

text: will

text: use

text: the

text: letter

text: ρ

text: to

text: denote

text: injection

text: rate;

text: we

text: require

text: the

text: inequalities

text: ρ

text: to

text: hold.

text: Let

text: ρ

text: be

text: an

text: injection

text: rate

text: and

text: w

text: a

text: positive

text: integer:

text: the

text: window

text: adversary

text: of

text: type

text: (ρ,

text: w)

text: may

text: inject

text: at

text: most

text: ρw

text: packets

text: in

text: each

text: contiguous

text: segment

text: of

text: w

text: rounds

text: into

text: any

text: set

text: of

text: stations;

text: the

text: number

text: w

text: is

text: called

text: the

text: window

text: size

text: in

text: such

text: a

text: context.

text: Let

text: ρ

text: be

text: an

text: injection

text: rate

text: and

text: b

text: a

text: non-negative

text: integer:

text: the

text: leaky-bucket

text: adversary

text: of

text: type

text: (ρ,

text: b)

text: may

text: inject

text: at

text: most

text: ρt

text: b

text: packets

text: in

text: every

text: contiguous

text: segment

text: of

text: t

text: rounds

text: into

text: any

text: set

text: of

text: stations.

text: An

text: adversary

text: is

text: said

text: to

text: be

text: of

text: injection

text: rate

text: ρ

text: when

text: it

text: is

text: either

text: of

text: window

text: type

text: (ρ,

text: w)

text: or

text: of

text: leaky-bucket-type

text: (ρ,

text: b),

text: for

text: some

text: w

text: and

text: b,

text: respectively.

text: The

text: window

text: adversary

text: of

text: type

text: (ρ,

text: w)

text: has

text: burstiness

text: ρw

text: The

text: leaky-bucket

text: adversary

text: of

text: type

text: (ρ,

text: b)

text: has

text: burstiness

text: ρ

text: b

text: Observe

text: that

text: injection

text: rate

text: larger

text: than

text: would

text: allow

text: the

text: adversary

text: to

text: make

text: the

text: number

text: of

text: packets

text: queued

text: at

text: stations

text: grow

text: unbounded,

text: as

text: at

text: most

text: one

text: packet

text: can

text: be

text: heard

text: per

text: round.

text: In

text: this

text: paper,

text: we

text: consider

text: only

text: adversaries

text: of

text: injection

text: rates

text: exactly

text: Such

text: adversaries

text: diﬀer

text: among

text: themselves

text: by

text: their

text: burstiness,

text: which

text: is

text: either

text: the

text: window

text: size

text: w

text: for

text: a

text: window

text: adversary,

text: or

text: the

text: number

text: for

text: a

text: leaky-bucket

text: adversary.

text: The

text: models

text: of

text: window

text: adversaries

text: and

text: leaky-bucket

text: ones

text: are

text: equivalent

text: for

text: injection

text: rates

text: strictly

text: less

text: than

text: while

text: the

text: leaky-bucket

text: adversary

text: of

text: injection

text: rate

text: can

text: generate

text: sequences

text: of

text: injections

text: not

text: captured

text: by

text: any

text: window

text: adversary

text: of

text: rate

text: as

text: was

text: showed

text: by

text: Ros´en

text: It

text: follows

text: that

text: a

text: possibility-type

text: of

text: a

text: result

text: for

text: leaky-bucket

text: adversaries

text: holds

text: automatically

text: for

text: window

text: adversaries,

text: while

text: an

text: impossibility

text: result

text: showed

text: for

text: window

text: adversaries

text: holds

text: automatically

text: for

text: leaky-bucket

text: adversaries.

text: Distributed

text: deterministic

text: broadcasting.

text: We

text: consider

text: broadcasting

text: algorithms

text: for

text: a

text: system

text: of

text: stations

text: attached

text: to

text: a

text: multiple

text: access

text: channel.

text: The

text: algorithms

text: are

text: restricted

text: to

text: be

text: both

text: distributed

text: and

text: deterministic.

text: Further

text: requirements

text: for

text: broadcast

text: algorithms

text: may

text: stem

text: from

text: additional

text: as-

text: sumptions

text: about

text: channels.

text: For

text: instance,

text: when

text: a

text: channel

text: is

text: equipped

text: with

text: a

text: collision

text: detection

text: mechanism

text: then

text: algorithms

text: need

text: to

text: be

text: able

text: to

text: react

text: diﬀerently

text: to

text: collisions

text: as

text: opposed

text: to

text: silent

text: rounds.

text: The

text: “slotted”

text: model

text: of

text: full

text: synchrony

text: does

text: not

text: impose

text: any

text: restrictions

text: on

text: speciﬁcations

text: of

text: algorithms:

text: stations

text: simply

text: act

text: driven

text: by

text: their

text: local

text: clocks.

text: On

text: the

text: other

text: hand,

text: the

text: quality

text: of

text: broadcasting,

text: for

text: instance

text: as

text: measured

text: by

text: the

text: maximum

text: throughput

text: achievable

text: for

text: a

text: given

text: number

text: of

text: stations,

text: may

text: be

text: aﬀected

text: by

text: the

text: level

text: of

text: synchrony

text: among

text: the

text: clocks

text: at

text: stations.

text: Any

text: deﬁnition

text: of

text: algorithms

text: needs

text: to

text: reﬂect

text: general

text: expectations

text: of

text: what

text: algorithms

text: are

text: to

text: accomplish.

text: We

text: simply

text: want

text: algorithms

text: to

text: facilitate

text: hearing

text: packets

text: on

text: a

text: channel,

text: in

text: a

text: distributed

text: and

text: deterministic

text: manner,

text: while

text: packets

text: are

text: injected

text: into

text: stations.

text: There

text: are

text: numerous

text: tacit

text: assumptions

text: in

text: such

text: expectations,

text: let

text: us

text: next

text: discuss

text: the

text: key

text: ones.

text: We

text: want

text: a

text: station

text: to

text: have

text: private

text: memory

text: to

text: store

text: incoming

text: packets

text: while

text: waiting

text: for

text: access


text: A PRIORI ERROR ESTIMATES FOR FINITE ELEMENT APPROXIMATIONS TO EIGENVALUES AND EIGENFUNCTIONS OF THE LAPLACE-BELTRAMI OPERATOR ∗ † ‡ ANDREA BONITO AND ALAN DEMLOW AND JUSTIN OWEN Abstract. Elliptic partial diﬀerential equations on surfaces play an essential role in geometry, relativity theory, phase transitions, materials science, image processing, and other applications. They are typically governed by the Laplace-Beltrami operator. We present and analyze approximations by Surface Finite Element Methods (SFEM) of the Laplace-Beltrami eigenvalue problem. As for SFEM for source problems, spectral approximation is challenged by two sources of errors: the geometric consistency error due to the approximation of the surface and the Galerkin error corresponding to ﬁnite element resolution of eigenfunctions. We show that these two error sources interact for eigenfunction approximations as for the source problem. The situation is diﬀerent for eigenvalues, where a novel situation occurs for the geometric consistency error: The degree of the geometric error depends on the choice of interpolation points used to construct the approximate surface. Thus the geometric consistency term can sometimes be made to converge faster than in the eigenfunction case through a judicious choice of interpolation points. Key words. Laplace-Beltrami operator; ﬁnite element method; eigenvalues and eigenvector approximation; cluster approximation; geometric error AMS subject classiﬁcation. 65N12, 65N15, 65N25, 65N30 The spectrum of the Laplacian is ubiquitous in the sciences and engineering. − Consider the eigenvalue problem ∆u = λu on a Euclidean domain Ω, with u = 0 on ≤ ≤ ≤ (cid:82) ∂Ω. There is then a sequence 0 < λ λ λ ... of eigenvalues with corresponding (cid:82) { 1} 2 3 V ⊂ L -orthonormal eigenfunctions u . Given a ﬁnite element space H1(Ω), the 2 i ∈ V × R ∇0 · ∇ natural ﬁnite element counterpart is to ﬁnd (U, Λ) + such that U V = ∈ V Ω Λ UV , V . Ω Finite element methods (FEM) are a natural and widely used tool for approxi- mating spectra of elliptic PDE. Analyzing the error behavior of such FEM is more challenging than for source problems because of the nonlinear nature of the problem. A priori error estimation for FEM approximations of the eigenvalues and eigenfunc- tions of the Laplacian and related operators in ﬂat (Euclidean) space is a classical topic in ﬁnite element theory; cf. [33, 15, 2, 3]. We highlight the review article [1] of Babuˇska and Osborn in this regard. These bounds are all asymptotic in the sense that they require an initial ﬁneness condition on the mesh. More recently, sharp bounds for eigenvalues (but not eigenfunctions) appeared in [27]. These bounds are notable because they are truly a priori in the sense that they do not require a suﬃciently ﬁne mesh. Finally, over the past decade a number of papers have appeared analyzing con- vergence and optimality of adaptive ﬁnite element methods (AFEM) for eigenvalue problems [18, 24, 14, 17, 23, 9]. Because sharp a priori estimates are needed in order to analyze AFEM optimality properties, some of these papers also contain improved ∗ DEPARTMENT OF MATHEMATICS, TEXAS A&M UNIVERSITY, COLLEGE STATION TX, 77843; EMAIL: BONITO@MATH.TAMU.EDU. PARTIALLY SUPPORTED BY NSF GRANT DMS- 1254618. † DEPARTMENT OF MATHEMATICS, TEXAS A&M UNIVERSITY, COLLEGE STATION TX, 77843; EMAIL: DEMLOW@MATH.TAMU.EDU. PARTIALLY SUPPORTED BY NSF GRANTS DMS- 1518925 AND DMS-1720369. ‡ DEPARTMENT OF MATHEMATICS, TEXAS A&M UNIVERSITY, COLLEGE STATION, TX, 77843; EMAIL: JOWEN6@MATH.TAMU.EDU. PARTIALLY SUPPORTED BY NSF GRANTS DMS- 1518925 AND DMS-1720369. 1 ##LTLine##

text: A

text: PRIORI

text: ERROR

text: ESTIMATES

text: FOR

text: FINITE

text: ELEMENT

text: APPROXIMATIONS

text: TO

text: EIGENVALUES

text: AND

text: EIGENFUNCTIONS

text: OF

text: THE

text: LAPLACE-BELTRAMI

text: OPERATOR

text: ANDREA

text: BONITO

text: AND

text: ALAN

text: DEMLOW

text: AND

text: JUSTIN

text: OWEN

text: Abstract.

text: Elliptic

label: abstract

text: partial

text: diﬀerential

text: equations

text: on

text: surfaces

text: play

text: an

text: essential

text: role

text: in

text: geometry,

text: relativity

text: theory,

text: phase

text: transitions,

text: materials

text: science,

text: image

text: processing,

text: and

text: other

text: applications.

text: They

text: are

text: typically

text: governed

text: by

text: the

text: Laplace-Beltrami

text: operator.

text: We

text: present

text: and

text: analyze

text: approximations

text: by

text: Surface

text: Finite

text: Element

text: Methods

text: (SFEM)

text: of

text: the

text: Laplace-Beltrami

text: eigenvalue

text: problem.

text: As

text: for

text: SFEM

text: for

text: source

text: problems,

text: spectral

text: approximation

text: is

text: challenged

text: by

text: two

text: sources

text: of

text: errors:

text: the

text: geometric

text: consistency

text: error

text: due

text: to

text: the

text: approximation

text: of

text: the

text: surface

text: and

text: the

text: Galerkin

text: error

text: corresponding

text: to

text: ﬁnite

text: element

text: resolution

text: of

text: eigenfunctions.

text: We

text: show

text: that

text: these

text: two

text: error

text: sources

text: interact

text: for

text: eigenfunction

text: approximations

text: as

text: for

text: the

text: source

text: problem.

text: The

text: situation

text: is

text: diﬀerent

text: for

text: eigenvalues,

text: where

text: a

text: novel

text: situation

text: occurs

text: for

text: the

text: geometric

text: consistency

text: error:

text: The

text: degree

text: of

text: the

text: geometric

text: error

text: depends

text: on

text: the

text: choice

text: of

text: interpolation

text: points

text: used

text: to

text: construct

text: the

text: approximate

text: surface.

text: Thus

text: the

text: geometric

text: consistency

text: term

text: can

text: sometimes

text: be

text: made

text: to

text: converge

text: faster

text: than

text: in

text: the

text: eigenfunction

text: case

text: through

text: a

text: judicious

text: choice

text: of

text: interpolation

text: points.

text: Key

text: words.

text: Laplace-Beltrami

text: operator;

text: ﬁnite

text: element

text: method;

text: eigenvalues

text: and

text: eigenvector

text: approximation;

text: cluster

text: approximation;

text: geometric

text: error

text: AMS

text: subject

text: classiﬁcation.

text: The

text: spectrum

text: of

text: the

text: Laplacian

text: is

text: ubiquitous

text: in

text: the

text: sciences

text: and

text: engineering.

text: Consider

text: the

text: eigenvalue

text: problem

text: ∆u

text: λu

text: on

text: a

text: Euclidean

text: domain

text: Ω,

text: with

text: u

text: on

text: ∂Ω.

text: There

text: is

text: then

text: a

text: sequence

text: λ

text: λ

text: λ

text: of

text: eigenvalues

text: with

text: corresponding

text: V

text: L

text: -orthonormal

text: eigenfunctions

text: u

text: Given

text: a

text: ﬁnite

text: element

text: space

text: the

text: i

text: V

text: R

text: ∇0

text: natural

text: ﬁnite

text: element

text: counterpart

text: is

text: to

text: ﬁnd

text: (U,

text: Λ)

text: such

text: that

text: U

text: V

text: V

text: Ω

text: Λ

text: UV

text: V

text: Ω

text: Finite

text: element

text: methods

text: (FEM)

text: are

text: a

text: natural

text: and

text: widely

text: used

text: tool

text: for

text: approxi-

text: mating

text: spectra

text: of

text: elliptic

text: PDE.

text: Analyzing

text: the

text: error

text: behavior

text: of

text: such

text: FEM

text: is

text: more

text: challenging

text: than

text: for

text: source

text: problems

text: because

text: of

text: the

text: nonlinear

text: nature

text: of

text: the

text: problem.

text: A

text: priori

text: error

text: estimation

text: for

text: FEM

text: approximations

text: of

text: the

text: eigenvalues

text: and

text: eigenfunc-

text: tions

text: of

text: the

text: Laplacian

text: and

text: related

text: operators

text: in

text: ﬂat

text: (Euclidean)

text: space

text: is

text: a

text: classical

text: topic

text: in

text: ﬁnite

text: element

text: theory;

text: cf.

text: We

text: highlight

text: the

text: review

text: article

text: of

text: Babuˇska

text: and

text: Osborn

text: in

text: this

text: regard.

text: These

text: bounds

text: are

text: all

text: asymptotic

text: in

text: the

text: sense

text: that

text: they

text: require

text: an

text: initial

text: ﬁneness

text: condition

text: on

text: the

text: mesh.

text: More

text: recently,

text: sharp

text: bounds

text: for

text: eigenvalues

text: (but

text: not

text: eigenfunctions)

text: appeared

text: in

text: These

text: bounds

text: are

text: notable

text: because

text: they

text: are

text: truly

text: a

text: priori

text: in

text: the

text: sense

text: that

text: they

text: do

text: not

text: require

text: a

text: suﬃciently

text: ﬁne

text: mesh.

text: Finally,

text: over

text: the

text: past

text: decade

text: a

text: number

text: of

text: papers

text: have

text: appeared

text: analyzing

text: con-

text: vergence

text: and

text: optimality

text: of

text: adaptive

text: ﬁnite

text: element

text: methods

text: (AFEM)

text: for

text: eigenvalue

text: problems

text: Because

text: sharp

text: a

text: priori

text: estimates

text: are

text: needed

text: in

text: order

text: to

text: analyze

text: AFEM

text: optimality

text: properties,

text: some

text: of

text: these

text: papers

text: also

text: contain

text: improved

text: DEPARTMENT

text: OF

text: MATHEMATICS,

text: TEXAS

text: A&M

text: UNIVERSITY,

text: COLLEGE

text: STATION

text: TX,

text: EMAIL:

text: BONITO@MATH.TAMU.EDU.

text: PARTIALLY

text: SUPPORTED

text: BY

text: NSF

text: GRANT

text: DMS-

text: DEPARTMENT

text: OF

text: MATHEMATICS,

text: TEXAS

text: A&M

text: UNIVERSITY,

text: COLLEGE

text: STATION

text: TX,

text: EMAIL:

text: DEMLOW@MATH.TAMU.EDU.

text: PARTIALLY

text: SUPPORTED

text: BY

text: NSF

text: GRANTS

text: DMS-

text: AND

text: DEPARTMENT

text: OF

text: MATHEMATICS,

text: TEXAS

text: A&M

text: UNIVERSITY,

text: COLLEGE

text: STATION,

text: TX,

text: EMAIL:

text: PARTIALLY

text: SUPPORTED

text: BY

text: NSF

text: GRANTS

text: DMS-

text: AND

text: ##LTLine##


text: FEM FOR LAPLACE-BELTRAMI EIGENVALUE PROBLEMS 15 (cid:104) (cid:105) We apply Young’s inequality again to arrive at (cid:102) (cid:102) (cid:102) (cid:107) (cid:107) (cid:46) (cid:107) − − (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) W 2 (1 + µ(J))2 u Gu α 2 + h2k+2 u 2 + h2k+2 u 2 , M i i M i M i m˜ h which yields the desired result upon taking a square root. { } Theorem 4.2 (L2 error estimate). Let λ ∈ be an exact eigenvalue cluster {j j} J V satisfying the separation assumption (2.4). Let Λ dim( #) be the set of approximate ∞ ∈j j=1 ∈ FEM eigenvalues satisfying µ(J) < . We ﬁx i J and denote by u H1 (γ) any ∈ R i # eigenfunction associated with λ . Then for any α , the following bound holds: i (cid:102) (cid:102) (cid:107) − − (cid:107) ≤ (cid:107) − − (cid:107) u P u α u Zu α (4.7) i i M (cid:46) i i (cid:107) −M − (cid:107)(cid:102) (cid:107) (cid:107)(cid:102) (1 + µ(J)) u Gu α + (1 + µ(J)) u hk+1. i i M i M (cid:102) W Proof. Because P α = Zα = 0 and P is the M-projection onto , we have # (cid:102) (cid:102) (cid:102) (cid:107) − − (cid:107) (cid:107) − − − (cid:107) ≤ (cid:107) − − − (cid:107) (u α) P u = u α P (u α) (u α) Z(u α) i i M (cid:107) i − − (cid:107)i (cid:102) ≤ (cid:107)M − i − (cid:107)(cid:102) (cid:107) i − M (cid:107)(cid:102) = u Zu α u Gu α + Gu Zu . i i M i i M i i M The second leg is bounded using Lemma 4.1. (cid:101) (cid:107) − (cid:107) We now focus on estimates for u Zu . i i{A } Theorem 4.3 (Energy estimate). Let λ ∈ be an exact eigenvalue cluster j{ j J} V satisfying the separation assumption (2.4). Let Λ dim( #) be a set of approximate ∞ ∈j j=1 ∈ FEM eigenvalues satisfying µ(J) < . We ﬁx i J and denote by u H1 (γ) any ∈ R i # eigenfunction associated with λ . Then for(cid:112)any α , the following bound holds: i (cid:101) (cid:112) (cid:101) (cid:102) (cid:107) − (cid:107) ≤ (cid:107) − (cid:107) (cid:107) − − (cid:107) u Zu u Gu + C λ (1 + µ(J)) u Gu α (4.8) i i A i i A i(cid:107) (cid:107)(cid:102) i i M + C λ (1 + µ(J))hk+1 u . i i M (cid:101) − (cid:107) (cid:107) Proof. Let W := Gu Zu . We restart from the estimate (4.6) for W , apply i i A Young’s inequality, and take advantage of the L2 error bound (4.1) to deduce (cid:101) (cid:102) (cid:102) (cid:102) (cid:107) (cid:107) (cid:46) (cid:107) (cid:107) (cid:107) − − (cid:107) (cid:107) (cid:107) W 2 λ (h2k+2 u 2 + u Gu α 2 + W 2 ) A i i M i (cid:102) i M M(cid:102) (cid:46) (cid:107) (cid:107) (cid:107) − − (cid:107) λ (1 + µ(J))2(h2k+2 u 2 + u Gu α 2 ). i (cid:101) i M i (cid:101) i M(cid:101) (cid:107) − (cid:107) ≤ (cid:107) − (cid:107) (cid:107) (cid:107) The desired result follows from u Zu u Gu + W . (cid:101) i i A i i A A V We end by commenting on (4.8). Because G is the Galerkin projection onto · · # with respect to A( , ), we have for the ﬁrst term in (4.8) that (cid:101) (cid:101) (cid:101) (cid:107) − (cid:107) ≤ (cid:107) − (cid:107) (cid:107) − (cid:107) (4.9) u Gu inf u V = inf u V . i i A ∈V i A ∈V i A V # V ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FEM

text: FOR

text: LAPLACE-BELTRAMI

text: EIGENVALUE

text: PROBLEMS

text: We

text: apply

text: Young’s

text: inequality

text: again

text: to

text: arrive

text: at

text: W

text: u

text: Gu

text: α

text: u

text: u

text: M

text: i

text: i

text: M

text: i

text: M

text: i

text: m˜

text: h

text: which

text: yields

text: the

text: desired

text: result

text: upon

text: taking

text: a

text: square

text: root.

text: Theorem

text: error

text: estimate).

text: Let

text: λ

text: be

text: an

text: exact

text: eigenvalue

text: cluster

text: {j

text: j}

text: J

text: V

text: satisfying

text: the

text: separation

text: assumption

text: Let

text: Λ

text: dim(

text: be

text: the

text: set

text: of

text: approximate

text: ∈j

text: FEM

text: eigenvalues

text: satisfying

text: µ(J)

text: We

text: ﬁx

text: i

text: J

text: and

text: denote

text: by

text: u

text: (γ)

text: any

text: R

text: i

text: eigenfunction

text: associated

text: with

text: λ

text: Then

text: for

text: any

text: α

text: the

text: following

text: bound

text: holds:

text: i

text: u

text: P

text: u

text: α

text: u

text: Zu

text: α

text: i

text: i

text: M

text: i

text: i

text: −M

text: µ(J))

text: u

text: Gu

text: α

text: µ(J))

text: u

text: i

text: i

text: M

text: i

text: M

text: W

text: Proof.

text: Because

text: P

text: α

text: Zα

text: and

text: P

text: is

text: the

text: M-projection

text: onto

text: we

text: have

text: (u

text: α)

text: P

text: u

text: u

text: α

text: P

text: (u

text: α)

text: (u

text: α)

text: Z(u

text: α)

text: i

text: i

text: M

text: i

text: i

text: i

text: M

text: u

text: Zu

text: α

text: u

text: Gu

text: α

text: Gu

text: Zu

text: i

text: i

text: M

text: i

text: i

text: M

text: i

text: i

text: M

text: The

text: second

text: leg

text: is

text: bounded

text: using

text: Lemma

text: We

text: now

text: focus

text: on

text: estimates

text: for

text: u

text: Zu

text: i

text: i{A

text: Theorem

text: (Energy

text: estimate).

text: Let

text: λ

text: be

text: an

text: exact

text: eigenvalue

text: cluster

text: j{

text: j

text: J}

text: V

text: satisfying

text: the

text: separation

text: assumption

text: Let

text: Λ

text: dim(

text: be

text: a

text: set

text: of

text: approximate

text: ∈j

text: FEM

text: eigenvalues

text: satisfying

text: µ(J)

text: We

text: ﬁx

text: i

text: J

text: and

text: denote

text: by

text: u

text: (γ)

text: any

text: R

text: i

text: eigenfunction

text: associated

text: with

text: λ

text: Then

text: α

text: the

text: following

text: bound

text: holds:

text: i

text: u

text: Zu

text: u

text: Gu

text: C

text: λ

text: µ(J))

text: u

text: Gu

text: α

text: i

text: i

text: A

text: i

text: i

text: A

text: i

text: i

text: M

text: C

text: λ

text: u

text: i

text: i

text: M

text: Proof.

text: Let

text: W

text: Gu

text: Zu

text: We

text: restart

text: from

text: the

text: estimate

text: for

text: W

text: apply

text: i

text: i

text: A

text: Young’s

text: inequality,

text: and

text: take

text: advantage

text: of

text: the

text: error

text: bound

text: to

text: deduce

text: W

text: λ

text: u

text: u

text: Gu

text: α

text: W

text: A

text: i

text: i

text: M

text: i

text: i

text: M

text: λ

text: u

text: u

text: Gu

text: α

text: i

text: i

text: M

text: i

text: i

text: The

text: desired

text: result

text: follows

text: from

text: u

text: Zu

text: u

text: Gu

text: W

text: i

text: i

text: A

text: i

text: i

text: A

text: A

text: V

text: We

text: end

text: by

text: commenting

text: on

text: Because

text: G

text: is

text: the

text: Galerkin

text: projection

text: onto

text: with

text: respect

text: to

text: A(

text: we

text: have

text: for

text: the

text: ﬁrst

text: term

text: in

text: that

text: u

text: Gu

text: inf

text: u

text: V

text: inf

text: u

text: V

text: i

text: i

text: A

text: ∈V

text: i

text: A

text: ∈V

text: i

text: A

text: V

text: V

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 24 A. BONITO, A. DEMLOW, AND J. OWEN We now apply equivalence of norms over ﬁnite dimensional spaces and scaling argu- | | me(cid:12)(cid:12)nts noting that(cid:12)(cid:12) Dαϕˆ = Dαψˆ(cid:88)= 0 for α > r to get (cid:12) (cid:12) { } min r,(cid:96) ≤ | | | | | | d(F T )QFT ϕˆψˆ W(cid:96),∞(Tˆ) −i(cid:88),j−=0≥ d(F T )QFT W(cid:96)−i−j,∞(Tˆ) ϕˆ Wi,∞(Tˆ) ψˆ Wj,∞(Tˆ) (cid:96) i j 0 { } min r,(cid:96) (cid:46) | | | | | | d(F T )QFT W(cid:96)−i−j,∞(Tˆ) ϕˆ Hi(Tˆ) ψˆ Hj(Tˆ). −i,j−=0≥ (cid:96) i j 0 Through standard arguments we have | | | | (cid:46) (cid:107) (cid:107) | | | | ϕˆ Hi(Tˆ) ψˆ Hj(Tˆ) hi+j QF−1 L∞(T) ϕˆ Hi(T) ψˆ Hj(T). T | | (cid:46) (cid:107) (cid:107) (cid:46) − Noting that QFT Wk,∞(Tˆ) hn+j a(cid:88)nd QF−T1 L∞(T) h n along with − − (cid:96) i j | | (cid:46) | | | | d(F T )QFT W(cid:96)−i−j,∞(Tˆ) QFT Wk,∞(Tˆ) d(F T ) W(cid:96)−i−j−k,∞(Tˆ) k=0 and | | (cid:46) − − − (cid:107) (cid:107) (cid:12) d(F T(cid:12)) W(cid:96)−i−j−k,∞(Tˆ) h(cid:96) i j k d W(cid:96)−i−j−k,∞(T) (cid:12) (cid:12) gives (cid:12) (cid:12) (cid:46) (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) d(F )Q ϕˆψˆ h(cid:96) d ∞ ϕ { } ψ { } , T FT W(cid:96),∞(Tˆ) W(cid:96), (Ω) Hmin r,(cid:96) (T) Hmin r,(cid:96) (T) which is the desired result. We now consider the eﬀects of constructing Γ by interpolating ψ. Lemma 6.6 (Superconvergent Geometric Consistency). Let QUAD be a degree − Tˆ { } (cid:96) 1, R point quadrature rule on the unit element with quadrature points qˆ R , ∈ V H ∈ ∞ N i i=1 V r(Γ) be degree-r function, and assume that d(x) W(cid:96), ( ). If the points { h} { } L(xj) nk in (2.6) and q L coincide and in addition L(xj) = ψ(xj), then j=1 (cid:101) i i=1 (6.18) |a(V, V ) −(cid:102)A(V, V )| ≤ h(cid:96) (cid:107)d(x)H(cid:107) ∞ |V |2 { } + O(h2k), WT(cid:96), (Γ) HTmin r,(cid:96) (Γ) | − | (cid:46) (cid:107) H(cid:107) | | (6.19) m(V, V ) M(V, V ) h(cid:96) d(x) WT(cid:96),∞(Γ) V 2HTmin{r,(cid:96)}(Γ) + O(h2k). T Here a subscript denotes a broken (elementwise) version of the given norm. and Ppraorotift.ioWnethperoﬁv(cid:12)(cid:12)(cid:12)(cid:12)r(cid:90)est(6in.1te9g)r.al(6b.a1s8e(cid:12)(cid:12)(cid:12)(cid:12))dfoolnlotw(cid:88)hse furnomd(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)e(cid:90)rsliyminilgarmaersghu.me(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)nts. Recalling (6.9) #elements H ≤ H V 2d(x) dΣ V 2d(x) dΣ . Γ j=1 Tj (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)(cid:90) (cid:12) (cid:12)(cid:90) (cid:12) Let q be a q(cid:12)uadrature point (cid:12)on T(cid:12) . By assumption L(q) = ψ(cid:0)(q), so d(q(cid:1))(cid:12)= 0 and (cid:12) (cid:12) (cid:12)j (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) H H − H V 2d(x) dΣ = V 2d(x) dΣ QUAD V 2d(x) Tj Tj Tj ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A.

text: BONITO,

text: A.

text: DEMLOW,

text: AND

text: J.

text: OWEN

text: We

text: now

text: apply

text: equivalence

text: of

text: norms

text: over

text: ﬁnite

text: dimensional

text: spaces

text: and

text: scaling

text: argu-

text: noting

text: Dαϕˆ

text: for

text: α

text: r

text: to

text: get

text: min

text: d(F

text: T

text: )QFT

text: ϕˆψˆ

text: d(F

text: T

text: )QFT

text: ϕˆ

text: Wi,∞(Tˆ)

text: ψˆ

text: Wj,∞(Tˆ)

text: i

text: j

text: min

text: d(F

text: T

text: )QFT

text: ϕˆ

text: Hi(Tˆ)

text: ψˆ

text: Hj(Tˆ).

text: i

text: j

text: Through

text: standard

text: arguments

text: we

text: have

text: ϕˆ

text: Hi(Tˆ)

text: ψˆ

text: Hj(Tˆ)

text: hi+j

text: L∞(T)

text: ϕˆ

text: Hi(T)

text: ψˆ

text: Hj(T).

text: T

text: Noting

text: that

text: QFT

text: Wk,∞(Tˆ)

text: hn+j

text: L∞(T)

text: h

text: n

text: along

text: with

text: i

text: j

text: d(F

text: T

text: )QFT

text: QFT

text: Wk,∞(Tˆ)

text: d(F

text: T

text: and

text: d(F

text: i

text: j

text: k

text: d

text: gives

text: d(F

text: )Q

text: ϕˆψˆ

text: d

text: ϕ

text: ψ

text: T

text: FT

text: (Ω)

text: Hmin

text: (T)

text: Hmin

text: (T)

text: which

text: is

text: the

text: desired

text: result.

text: We

text: now

text: consider

text: the

text: eﬀects

text: of

text: constructing

text: Γ

text: by

text: interpolating

text: ψ.

text: Lemma

text: (Superconvergent

text: Geometric

text: Consistency).

text: Let

text: QUAD

text: be

text: a

text: degree

text: Tˆ

text: R

text: point

text: quadrature

text: rule

text: on

text: the

text: unit

text: element

text: with

text: quadrature

text: points

text: qˆ

text: R

text: V

text: H

text: N

text: i

text: V

text: r(Γ)

text: be

text: degree-r

text: function,

text: and

text: assume

text: that

text: d(x)

text: If

text: the

text: points

text: h}

text: L(xj)

text: nk

text: in

text: and

text: q

text: L

text: coincide

text: and

text: in

text: addition

text: L(xj)

text: ψ(xj),

text: then

text: i

text: |a(V,

text: V

text: V

text: |V

text: (Γ)

text: HTmin

text: (Γ)

text: m(V,

text: V

text: M(V,

text: V

text: d(x)

text: V

text: T

text: Here

text: a

text: subscript

text: denotes

text: a

text: broken

text: (elementwise)

text: version

text: of

text: the

text: given

text: norm.

text: and

text: Recalling

text: #elements

text: H

text: H

text: V

text: dΣ

text: V

text: dΣ

text: Γ

text: Tj

text: Let

text: q

text: be

text: a

text: point

text: By

text: assumption

text: L(q)

text: so

text: and

text: H

text: H

text: H

text: V

text: dΣ

text: V

text: dΣ

text: QUAD

text: V

text: Tj

text: Tj

text: Tj

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: First, dihedral angles appearing in the internal coordinate description must be treated to eliminate the circular periodicity, typically by expressing each angle as a vector on the unit circle, adding complexity to the molecular description101. Second, the impact of each internal coordinate upon the reconstruction error deﬁned in Eqn. 3 can be strongly heterogeneous, leading to strong biases in the trained network towards particular degrees of freedom. For example, a unit change in a dihedral angle in the middle of the biomolecule will typically lead to much larger structural perturbations than an equivalent change in an angle near the end of the chain. It is challenging to design error functions to compensate for these eﬀects. In this work, we instead confront the elimination of rotational invariances using data augmentation approach that is commonly used in deep learning to eliminate invariances and enhance training sets, and which has proved particularly valuable in image classiﬁcation applications103. For each translationally-centered molecular conﬁguration z , we generate an q ensemble of N additional conﬁgurations constructed by applying random three-dimensional rotations to z . In training the autoencoder we then assert that the network learn that all q of these inputs should “autoencode” to the same output, thereby teaching the network to disregard rotations as a relevant degree of freedom and discover CVs that are a function only of the internal molecular conﬁguration. Mathematically, this requires that we modify the error function deﬁned in Eqn. 3 to, (cid:88) (cid:88) (cid:88) (cid:16) (cid:17) Q N (cid:107) − (cid:107) 2 E = R (z ) L (zˆ , z ) 2 + λ w(i) , (5) n q q ref i jk q=1 n=1 i,j,k where R denotes a rotation of conﬁguration z by a randomly selected angle θ = [0, 2π) n q n around a randomly selected axis u in 3D space, and L (zˆ , z ) represents the optimal ro- n q ref tational alignment of the output of the autoencoder zˆ to a reference conﬁguration z that q ref has been previously translated such that its center of mass is coincident with the origin. The operation L (zˆ , z ) can be eﬃciently performed using the Kabsch algorithm99. Train- q ref ing of the autoencoder weights and biases to minimize Eqn. 5 teaches the network to map arbitrary rotations of a particular conﬁguration to the alignment of that conﬁguration to a speciﬁc reference structure. A deﬁciency of this approach is that we must select a particular 12

text: First,

text: dihedral

text: angles

text: appearing

text: in

text: the

text: internal

text: coordinate

text: description

text: must

text: be

text: treated

text: to

text: eliminate

text: the

text: circular

text: periodicity,

text: typically

text: by

text: expressing

text: each

text: angle

text: as

text: a

text: vector

text: on

text: the

text: unit

text: circle,

text: adding

text: complexity

text: to

text: the

text: molecular

text: Second,

text: the

text: impact

text: of

text: each

text: internal

text: coordinate

text: upon

text: the

text: reconstruction

text: error

text: deﬁned

text: in

text: Eqn.

text: can

text: be

text: strongly

text: heterogeneous,

text: leading

text: to

text: strong

text: biases

text: in

text: the

text: trained

text: network

text: towards

text: particular

text: degrees

text: of

text: freedom.

text: For

text: example,

text: a

text: unit

text: change

text: in

text: a

text: dihedral

text: angle

text: in

text: the

text: middle

text: of

text: the

text: biomolecule

text: will

text: typically

text: lead

text: to

text: much

text: larger

text: structural

text: perturbations

text: than

text: an

text: equivalent

text: change

text: in

text: an

text: angle

text: near

text: the

text: end

text: of

text: the

text: chain.

text: It

text: is

text: challenging

text: to

text: design

text: error

text: functions

text: to

text: compensate

text: for

text: these

text: eﬀects.

text: In

text: this

text: work,

text: we

text: instead

text: confront

text: the

text: elimination

text: of

text: rotational

text: invariances

text: using

text: data

text: augmentation

text: approach

text: that

text: is

text: commonly

text: used

text: in

text: deep

text: learning

text: to

text: eliminate

text: invariances

text: and

text: enhance

text: training

text: sets,

text: and

text: which

text: has

text: proved

text: particularly

text: valuable

text: in

text: image

text: classiﬁcation

text: For

text: each

text: translationally-centered

text: molecular

text: conﬁguration

text: z

text: we

text: generate

text: an

text: q

text: ensemble

text: of

text: N

text: additional

text: conﬁgurations

text: constructed

text: by

text: applying

text: random

text: three-dimensional

text: rotations

text: to

text: z

text: In

text: training

text: the

text: autoencoder

text: we

text: then

text: assert

text: that

text: the

text: network

text: learn

text: that

text: all

text: q

text: of

text: these

text: inputs

text: should

text: “autoencode”

text: to

text: the

text: same

text: output,

text: thereby

text: teaching

text: the

text: network

text: to

text: disregard

text: rotations

text: as

text: a

text: relevant

text: degree

text: of

text: freedom

text: and

text: discover

text: CVs

text: that

text: are

text: a

text: function

text: only

text: of

text: the

text: internal

text: molecular

text: conﬁguration.

text: Mathematically,

text: this

text: requires

text: that

text: we

text: modify

text: the

text: error

text: function

text: deﬁned

text: in

text: Eqn.

text: to,

text: Q

text: N

text: E

text: R

text: (z

text: L

text: (zˆ

text: z

text: λ

text: w(i)

text: n

text: q

text: q

text: ref

text: i

text: jk

text: i,j,k

text: where

text: R

text: denotes

text: a

text: rotation

text: of

text: conﬁguration

text: z

text: by

text: a

text: randomly

text: selected

text: angle

text: θ

text: n

text: q

text: n

text: around

text: a

text: randomly

text: selected

text: axis

text: u

text: in

text: space,

text: and

text: L

text: (zˆ

text: z

text: represents

text: the

text: optimal

text: ro-

text: n

text: q

text: ref

text: tational

text: alignment

text: of

text: the

text: output

text: of

text: the

text: autoencoder

text: zˆ

text: to

text: a

text: reference

text: conﬁguration

text: z

text: that

text: q

text: ref

text: has

text: been

text: previously

text: translated

text: such

text: that

text: its

text: center

text: of

text: mass

text: is

text: coincident

text: with

text: the

text: origin.

text: The

text: operation

text: L

text: (zˆ

text: z

text: can

text: be

text: eﬃciently

text: performed

text: using

text: the

text: Kabsch

text: Train-

text: q

text: ref

text: ing

text: of

text: the

text: autoencoder

text: weights

text: and

text: biases

text: to

text: minimize

text: Eqn.

text: teaches

text: the

text: network

text: to

text: map

text: arbitrary

text: rotations

text: of

text: a

text: particular

text: conﬁguration

text: to

text: the

text: alignment

text: of

text: that

text: conﬁguration

text: to

text: a

text: speciﬁc

text: reference

text: structure.

text: A

text: deﬁciency

text: of

text: this

text: approach

text: is

text: that

text: we

text: must

text: select

text: a

text: particular


text: parameters. Its success, however, depends crucially on the a priori availability of “good” CVs coincident with the important collective motions that separate metastable states5. It is diﬃcult to intuit these order parameters for all but the simplest systems, and CV biasing tends to fail badly for poor CV choices. Machine learning presents a systematic means to discover data-driven CVs. Conceptu- ally, these approaches posit that the molecular dynamics in the 3N-dimensional space of the Cartesian coordinates of the N atoms are eﬀectively restrained to low-dimensional “intrinsic manifold” containing the slow dynamics to which the remaining fast degrees of freedom are slaved4,42. The validity of this assumption has been demonstrated many times and corre- sponds to the emergence of a small number of collective modes from cooperative couplings between system degrees of freedom42–50. CV discovery algorithms are therefore essentially dimensionality reduction or manifold learning approaches4,43, and the CVs are “good” in that they correspond to slow collective motions of the system43,44. Data-driven CV discov- ery suﬀers from a fundamental diﬃculty: to perform good sampling of conﬁgurational space one requires good CVs that are explicit functions of the atomic coordinates, but to discover these CVs one needs to perform good sampling of conﬁgurational space to generate data for CV discovery. This is the root of the biased sampling “chicken-and-egg problem” iden- tiﬁed by Clementi and co-workers4. Accordingly, data-driven CV discovery must typically be performed in an iterative fashion by interleaving rounds of accelerated sampling and CV discovery: each round of sampling provides more comprehensive sampling of conﬁgurational space, and each round of CV discovery determines collective variables parameterizing the slow dynamical motions over the space explored by the biased calculations. Linear dimensionality reduction approaches such as principal components analysis (PCA)47,50,51 and multidimensional scaling (MDS)52 are straightforward to apply, and furnish CVs that are explicit functions of the atomic coordinates. As inherently linear approaches, however, the CVs are typically poor descriptors for complex biomolecules possessing convoluted and nonlinear intrinsic manifolds4,43,44. Kernel PCA presents a means to alleviate this problem by applying a known nonlinear transformation of the atomic coordinates prior to dimen- sionality reduction53, but the speciﬁcation of appropriate kernels can be almost as diﬃ- cult as intuiting the CVs themselves43. Nonlinear manifold learning approaches include 4

text: parameters.

text: Its

text: success,

text: however,

text: depends

text: crucially

text: on

text: the

text: a

text: priori

text: availability

text: of

text: “good”

text: CVs

text: coincident

text: with

text: the

text: important

text: collective

text: motions

text: that

text: separate

text: metastable

text: It

text: is

text: diﬃcult

text: to

text: intuit

text: these

text: order

text: parameters

text: for

text: all

text: but

text: the

text: simplest

text: systems,

text: and

text: CV

text: biasing

text: tends

text: to

text: fail

text: badly

text: for

text: poor

text: CV

text: choices.

text: Machine

text: learning

text: presents

text: a

text: systematic

text: means

text: to

text: discover

text: data-driven

text: CVs.

text: Conceptu-

text: ally,

text: these

text: approaches

text: posit

text: that

text: the

text: molecular

text: dynamics

text: in

text: the

text: space

text: of

text: the

text: Cartesian

text: coordinates

text: of

text: the

text: N

text: atoms

text: are

text: eﬀectively

text: restrained

text: to

text: low-dimensional

text: “intrinsic

text: manifold”

text: containing

text: the

text: slow

text: dynamics

text: to

text: which

text: the

text: remaining

text: fast

text: degrees

text: of

text: freedom

text: are

text: The

text: validity

text: of

text: this

text: assumption

text: has

text: been

text: demonstrated

text: many

text: times

text: and

text: corre-

text: sponds

text: to

text: the

text: emergence

text: of

text: a

text: small

text: number

text: of

text: collective

text: modes

text: from

text: cooperative

text: couplings

text: between

text: system

text: degrees

text: of

text: CV

text: discovery

text: algorithms

text: are

text: therefore

text: essentially

text: dimensionality

text: reduction

text: or

text: manifold

text: learning

text: and

text: the

text: CVs

text: are

text: “good”

text: in

text: that

text: they

text: correspond

text: to

text: slow

text: collective

text: motions

text: of

text: the

text: Data-driven

text: CV

text: discov-

text: ery

text: suﬀers

text: from

text: a

text: fundamental

text: diﬃculty:

text: to

text: perform

text: good

text: sampling

text: of

text: conﬁgurational

text: space

text: one

text: requires

text: good

text: CVs

text: that

text: are

text: explicit

text: functions

text: of

text: the

text: atomic

text: coordinates,

text: but

text: to

text: discover

text: these

text: CVs

text: one

text: needs

text: to

text: perform

text: good

text: sampling

text: of

text: conﬁgurational

text: space

text: to

text: generate

text: data

text: for

text: CV

text: discovery.

text: This

text: is

text: the

text: root

text: of

text: the

text: biased

text: sampling

text: “chicken-and-egg

text: problem”

text: iden-

text: tiﬁed

text: by

text: Clementi

text: and

text: Accordingly,

text: data-driven

text: CV

text: discovery

text: must

text: typically

text: be

text: performed

text: in

text: an

text: iterative

text: fashion

text: by

text: interleaving

text: rounds

text: of

text: accelerated

text: sampling

text: and

text: CV

text: discovery:

text: each

text: round

text: of

text: sampling

text: provides

text: more

text: comprehensive

text: sampling

text: of

text: conﬁgurational

text: space,

text: and

text: each

text: round

text: of

text: CV

text: discovery

text: determines

text: collective

text: variables

text: parameterizing

text: the

text: slow

text: dynamical

text: motions

text: over

text: the

text: space

text: explored

text: by

text: the

text: biased

text: calculations.

text: Linear

text: dimensionality

text: reduction

text: approaches

text: such

text: as

text: principal

text: components

text: analysis

text: and

text: multidimensional

text: scaling

text: are

text: straightforward

text: to

text: apply,

text: and

text: furnish

text: CVs

text: that

text: are

text: explicit

text: functions

text: of

text: the

text: atomic

text: coordinates.

text: As

text: inherently

text: linear

text: approaches,

text: however,

text: the

text: CVs

text: are

text: typically

text: poor

text: descriptors

text: for

text: complex

text: biomolecules

text: possessing

text: convoluted

text: and

text: nonlinear

text: intrinsic

text: Kernel

text: PCA

text: presents

text: a

text: means

text: to

text: alleviate

text: this

text: problem

text: by

text: applying

text: a

text: known

text: nonlinear

text: transformation

text: of

text: the

text: atomic

text: coordinates

text: prior

text: to

text: dimen-

text: sionality

text: but

text: the

text: speciﬁcation

text: of

text: appropriate

text: kernels

text: can

text: be

text: almost

text: as

text: diﬃ-

text: cult

text: as

text: intuiting

text: the

text: CVs

text: Nonlinear

text: manifold

text: learning

text: approaches

text: include


text: local tangent space alignment54, locally linear embedding (LLE)55,56, Isomap48,57–59, Lapla- cian eigenmaps60, Hessian eigenmaps61, semideﬁnite embedding (SDE) / maximum variance unfolding (MVU)58, diﬀusion maps44,62–65, and sketch maps66–68. These approaches have demonstrated great success in parameterizing nonlinear intrinsic manifolds of complex bio- and macromolecules by discovering nonlinear CVs corresponding to concerted structural mo- tions44,48,49,62,64,65,69–71. For the purposes of CV biasing, however, these approaches all share the critical deﬁciency in that they do not furnish the mapping of atomic coordinates to the CVs. An explicit and diﬀerentiable mapping from the atomic coordinates to the CVs is required to perform biased MD simulations in the CVs in order to propagate biasing forces in the CVs to forces on atoms1,4,43,72,73. (Biased Monte-Carlo requires that the CVs be ex- plicit, but not necessarily diﬀerentiable, functions.) Without this mapping, it is not possible perform biasing directly in CVs discovered by nonlinear learning. A small number of approaches have been developed to perform indirect and approximate biasing in CVs for which the atomic mapping is unknown. We previously introduced perhaps the simplest approach that correlates CVs with candidate physical variables (e.g., dihedral angles, radius of gyration) and performs biased sampling in these proxy variables62. High- throughput screening can sieve putative physical variables and identify those best correlated with the CVs74–76. This approach is, however, typically rather unsatisfactory, since it sur- renders sampling in the CVs, and is very sensitive to the quality of the physical proxies. A related approach ﬁts the parameters of CVs with predeﬁned functional forms77, but the deﬁnition of appropriate functions can almost as diﬃcult as deﬁning the CVs themselves. A more sophisticated approach expresses atomic coordinates as a sum of localized basis func- tions over a small number of “landmarks” in the CV embedding1,59,72,78, and projects new data by performing a weighted nearest-neighbors embedding72,78 or solving a linear opti- mization problem to minimize the projection error1,59. Accordingly, direct sampling in the CVs is relinquished for an interpolative and approximate basis function expansion43. An el- egant strategy termed diﬀusion-map-directed molecular dynamics (DM-d-MD) proposed by Clementi and co-workers accelerates sampling by initializing unbiased simulations in poorly sampled regions of the CV projection65,71. Kevrekidis and co-workers recently proposed in- trinsic map dynamics (iMapD) as an ingenious approach that ﬁrst employs diﬀusion maps 5

text: local

text: tangent

text: space

text: locally

text: linear

text: embedding

text: Lapla-

text: cian

text: Hessian

text: semideﬁnite

text: embedding

text: (SDE)

text: maximum

text: variance

text: unfolding

text: diﬀusion

text: and

text: sketch

text: These

text: approaches

text: have

text: demonstrated

text: great

text: success

text: in

text: parameterizing

text: nonlinear

text: intrinsic

text: manifolds

text: of

text: complex

text: bio-

text: and

text: macromolecules

text: by

text: discovering

text: nonlinear

text: CVs

text: corresponding

text: to

text: concerted

text: structural

text: mo-

text: For

text: the

text: purposes

text: of

text: CV

text: biasing,

text: however,

text: these

text: approaches

text: all

text: share

text: the

text: critical

text: deﬁciency

text: in

text: that

text: they

text: do

text: not

text: furnish

text: the

text: mapping

text: of

text: atomic

text: coordinates

text: to

text: the

text: CVs.

text: An

text: explicit

text: and

text: diﬀerentiable

text: mapping

text: from

text: the

text: atomic

text: coordinates

text: to

text: the

text: CVs

text: is

text: required

text: to

text: perform

text: biased

text: MD

text: simulations

text: in

text: the

text: CVs

text: in

text: order

text: to

text: propagate

text: biasing

text: forces

text: in

text: the

text: CVs

text: to

text: forces

text: on

text: (Biased

text: Monte-Carlo

text: requires

text: that

text: the

text: CVs

text: be

text: ex-

text: plicit,

text: but

text: not

text: necessarily

text: diﬀerentiable,

text: functions.)

text: Without

text: this

text: mapping,

text: it

text: is

text: not

text: possible

text: perform

text: biasing

text: directly

text: in

text: CVs

text: discovered

text: by

text: nonlinear

text: learning.

text: A

text: small

text: number

text: of

text: approaches

text: have

text: been

text: developed

text: to

text: perform

text: indirect

text: and

text: approximate

text: biasing

text: in

text: CVs

text: for

text: which

text: the

text: atomic

text: mapping

text: is

text: unknown.

text: We

text: previously

text: introduced

text: perhaps

text: the

text: simplest

text: approach

text: that

text: correlates

text: CVs

text: with

text: candidate

text: physical

text: variables

text: (e.g.,

text: dihedral

text: angles,

text: radius

text: of

text: gyration)

text: and

text: performs

text: biased

text: sampling

text: in

text: these

text: proxy

text: High-

text: throughput

text: screening

text: can

text: sieve

text: putative

text: physical

text: variables

text: and

text: identify

text: those

text: best

text: correlated

text: with

text: the

text: This

text: approach

text: is,

text: however,

text: typically

text: rather

text: unsatisfactory,

text: since

text: it

text: sur-

text: renders

text: sampling

text: in

text: the

text: CVs,

text: and

text: is

text: very

text: sensitive

text: to

text: the

text: quality

text: of

text: the

text: physical

text: proxies.

text: A

text: related

text: approach

text: ﬁts

text: the

text: parameters

text: of

text: CVs

text: with

text: predeﬁned

text: functional

text: but

text: the

text: deﬁnition

text: of

text: appropriate

text: functions

text: can

text: almost

text: as

text: diﬃcult

text: as

text: deﬁning

text: the

text: CVs

text: themselves.

text: A

text: more

text: sophisticated

text: approach

text: expresses

text: atomic

text: coordinates

text: as

text: a

text: sum

text: of

text: localized

text: basis

text: func-

text: tions

text: over

text: a

text: small

text: number

text: of

text: “landmarks”

text: in

text: the

text: CV

text: and

text: projects

text: new

text: data

text: by

text: performing

text: a

text: weighted

text: nearest-neighbors

text: or

text: solving

text: a

text: linear

text: opti-

text: mization

text: problem

text: to

text: minimize

text: the

text: projection

text: Accordingly,

text: direct

text: sampling

text: in

text: the

text: CVs

text: is

text: relinquished

text: for

text: an

text: interpolative

text: and

text: approximate

text: basis

text: function

text: An

text: el-

text: egant

text: strategy

text: termed

text: diﬀusion-map-directed

text: molecular

text: dynamics

text: (DM-d-MD)

text: proposed

text: by

text: Clementi

text: and

text: co-workers

text: accelerates

text: sampling

text: by

text: initializing

text: unbiased

text: simulations

text: in

text: poorly

text: sampled

text: regions

text: of

text: the

text: CV

text: Kevrekidis

text: and

text: co-workers

text: recently

text: proposed

text: in-

text: trinsic

text: map

text: dynamics

text: (iMapD)

text: as

text: an

text: ingenious

text: approach

text: that

text: ﬁrst

text: employs

text: diﬀusion

text: maps


text: 56. Zhang, Z. and Wang, J. In Advances in Neural Information Processing Systems, pages 1593–1600, 2007. 57. Tenenbaum, J. B.; De Silva, V. and Langford, J. C., Science, 2000, 290(5500), 2319– 2323. 58. Weinberger, K. Q. and Saul, L. K., International Journal of Computer Vision, 2006, 70(1), 77–90. 59. Li, C.-g.; Guo, J.; Chen, G.; Nie, X.-f. and Yang, Z. In 2006 International Conference on Machine Learning and Cybernetics, pages 3201–3206. IEEE, 2006. 60. Belkin, M. and Niyogi, P. In Advances in Neural Information Processing Systems, pages 585–591, 2002. 61. Donoho, D. L. and Grimes, C., Proceedings of the National Academy of Sciences, 2003, 100(10), 5591–5596. 62. Ferguson, A. L.; Panagiotopoulos, A. Z.; Debenedetti, P. G. and Kevrekidis, I. G., The Journal of Chemical Physics, 2011, 134(13), 135103. 63. Coifman, R. R. and Lafon, S., Applied and Computational Harmonic Analysis, 2006, 21(1), 5–30. 64. Rohrdanz, M. A.; Zheng, W.; Maggioni, M. and Clementi, C., The Journal of Chemical Physics, 2011, 134(12), 03B624. 65. Preto, J. and Clementi, C., Physical Chemistry Chemical Physics, 2014, 16(36), 19181– 19191. 66. Ceriotti, M.; Tribello, G. A. and Parrinello, M., Proceedings of the National Academy of Sciences, 2011, 108(32), 13023–13028. 67. Tribello, G. A.; Ceriotti, M. and Parrinello, M., Proceedings of the National Academy of Sciences, 2012, 109(14), 5196–5201. 57

label: reference

text: Zhang,

text: Z.

text: and

text: Wang,

text: J.

text: In

text: Advances

text: in

text: Neural

text: Information

text: Processing

text: Systems,

text: pages

text: Tenenbaum,

text: J.

text: B.;

text: De

text: Silva,

text: V.

text: and

text: Langford,

text: J.

text: C.,

text: Science,

text: Weinberger,

text: K.

text: Q.

text: and

text: Saul,

text: L.

text: K.,

text: International

text: Journal

text: of

text: Computer

text: Vision,

text: Li,

text: C.-g.;

text: Guo,

text: J.;

text: Chen,

text: G.;

text: Nie,

text: X.-f.

text: and

text: Yang,

text: Z.

text: In

text: International

text: Conference

text: on

text: Machine

text: Learning

text: and

text: Cybernetics,

text: pages

text: IEEE,

text: Belkin,

text: M.

text: and

text: Niyogi,

text: P.

text: In

text: Advances

text: in

text: Neural

text: Information

text: Processing

text: Systems,

text: pages

text: Donoho,

text: D.

text: L.

text: and

text: Grimes,

text: C.,

text: Proceedings

text: of

text: the

text: National

text: Academy

text: of

text: Sciences,

text: Ferguson,

text: A.

text: L.;

text: Panagiotopoulos,

text: A.

text: Z.;

text: Debenedetti,

text: P.

text: G.

text: and

text: Kevrekidis,

text: I.

text: G.,

text: The

text: Journal

text: of

text: Chemical

text: Physics,

text: Coifman,

text: R.

text: R.

text: and

text: Lafon,

text: S.,

text: Applied

text: and

text: Computational

text: Harmonic

text: Analysis,

text: Rohrdanz,

text: M.

text: A.;

text: Zheng,

text: W.;

text: Maggioni,

text: M.

text: and

text: Clementi,

text: C.,

text: The

text: Journal

text: of

text: Chemical

text: Physics,

text: Preto,

text: J.

text: and

text: Clementi,

text: C.,

text: Physical

text: Chemistry

text: Chemical

text: Physics,

text: Ceriotti,

text: M.;

text: Tribello,

text: G.

text: A.

text: and

text: Parrinello,

text: M.,

text: Proceedings

text: of

text: the

text: National

text: Academy

text: of

text: Sciences,

text: Tribello,

text: G.

text: A.;

text: Ceriotti,

text: M.

text: and

text: Parrinello,

text: M.,

text: Proceedings

text: of

text: the

text: National

text: Academy

text: of

text: Sciences,


text: 142. Whitney, H., Annals of Mathematics, 1936, pages 645–680. 143. Broomhead, D. S. and King, G. P., Physica D: Nonlinear Phenomena, 1986, 20(2-3), 217–236. 144. Kim, S. B.; Dsilva, C. J.; Kevrekidis, I. G. and Debenedetti, P. G., The Journal of Chemical Physics, 2015, 142(8), 085101. 145. Qiu, L.; Pabit, S. A.; Roitberg, A. E. and Hagen, S. J., Journal of the American Chemical Society, 2002, 124(44), 12952–12953. 146. Seshasayee, A. S. N., Theoretical Biology and Medical Modelling, 2005, 2(1), 7. 147. Heyda, J.; Kozisek, M.; Bedn´arova, L.; Thompson, G.; Konvalinka, J.; Vondrasek, J. and Jungwirth, P., The Journal of Physical Chemistry B, 2011, 115(28), 8910–8924. 148. Juraszek, J. and Bolhuis, P., Proceedings of the National Academy of Sciences, 2006, 103(43), 15859–15864. 149. Kim, S. B.; Gupta, D. R. and Debenedetti, P. G., Scientiﬁc Reports, 2016, 6, 25612. 150. Hatch, H. W.; Stillinger, F. H. and Debenedetti, P. G., The Journal of Physical Chem- istry B, 2014, 118(28), 7761–7769. 151. Kannan, S. and Zacharias, M., PloS ONE, 2014, 9(2), e88383. 152. Schug, A.; Wenzel, W. and Hansmann, U. H., The Journal of Chemical Physics, 2005, 122(19), 194711. 153. Snow, C. D.; Zagrovic, B. and Pande, V. S., Journal of the American Chemical Society, 2002, 124(49), 14548–14549. 154. Zhou, R., Proceedings of the National Academy of Sciences, 2003, 100(23), 13280– 13285. 155. Zhou, R., Proteins: Structure, Function, and Bioinformatics, 2003, 53(2), 148–161. 64

text: Whitney,

text: H.,

text: Annals

text: of

text: Mathematics,

text: pages

text: Broomhead,

text: D.

text: S.

text: and

text: King,

text: G.

text: P.,

text: Physica

text: D:

text: Nonlinear

text: Phenomena,

text: Kim,

text: S.

text: B.;

text: Dsilva,

text: C.

text: J.;

text: Kevrekidis,

text: I.

text: G.

text: and

text: Debenedetti,

text: P.

text: G.,

text: The

text: Journal

text: of

text: Chemical

text: Physics,

text: Qiu,

text: L.;

text: Pabit,

text: S.

text: A.;

text: Roitberg,

text: A.

text: E.

text: and

text: Hagen,

text: S.

text: J.,

text: Journal

text: of

text: the

text: American

text: Chemical

text: Society,

text: Seshasayee,

text: A.

text: S.

text: N.,

text: Theoretical

text: Biology

text: and

text: Medical

text: Modelling,

text: Heyda,

text: J.;

text: Kozisek,

text: M.;

text: Bedn´arova,

text: L.;

text: Thompson,

text: G.;

text: Konvalinka,

text: J.;

text: Vondrasek,

text: J.

text: and

text: Jungwirth,

text: P.,

text: The

text: Journal

text: of

text: Physical

text: Chemistry

text: B,

text: Juraszek,

text: J.

text: and

text: Bolhuis,

text: P.,

text: Proceedings

text: of

text: the

text: National

text: Academy

text: of

text: Sciences,

text: Kim,

text: S.

text: B.;

text: Gupta,

text: D.

text: R.

text: and

text: Debenedetti,

text: P.

text: G.,

text: Scientiﬁc

text: Reports,

text: Hatch,

text: H.

text: W.;

text: Stillinger,

text: F.

text: H.

text: and

text: Debenedetti,

text: P.

text: G.,

text: The

text: Journal

text: of

text: Physical

text: Chem-

text: istry

text: B,

text: Kannan,

text: S.

text: and

text: Zacharias,

text: M.,

text: PloS

text: ONE,

text: Schug,

text: A.;

text: Wenzel,

text: W.

text: and

text: Hansmann,

text: U.

text: H.,

text: The

text: Journal

text: of

text: Chemical

text: Physics,

text: Snow,

text: C.

text: D.;

text: Zagrovic,

text: B.

text: and

text: Pande,

text: V.

text: S.,

text: Journal

text: of

text: the

text: American

text: Chemical

text: Society,

text: Zhou,

text: R.,

text: Proceedings

text: of

text: the

text: National

text: Academy

text: of

text: Sciences,

text: Zhou,

text: R.,

text: Proteins:

text: Structure,

text: Function,

text: and

text: Bioinformatics,


text: (cid:88) (cid:88) (cid:16) (cid:17) (cid:88) (cid:88) (cid:16) (cid:17) Q Q (cid:107) − (cid:107) 2 (cid:107) − ◦ (cid:107) 2 E = z zˆ 2 + λ w(i) = z (Θ Θ )z 2 + λ w(i) . (3) q q i jk q rec proj q i jk q=1 i,j,k q=1 i,j,k The ﬁrst term is the reconstruction error, and the second a regularizing penalty known as weight decay that stabilizes ﬁtting by controlling the growth of the network weights81,94. In this work, we ﬁnd our ﬁtting procedure to be stable in the absence of weight decay, and choose to set λ = 0 for all layers. Minimization of E is performed using the backpropagation i algorithm that employs gradient descent to propagate errors in the output back through the network and iteratively tune the network parameters88,95. In this work, our training is per- formed by mini-batch stochastic gradient descent with momentum96,97. To avoid overﬁtting, we randomly pick 80% of data as the training set, and remaining 20% as the validation set. Training is terminated when either we reach maximum number of training epochs, or the validation error no longer decreases for a 30 continuous epochs (i.e., early stopping). Dimensionality determination. The number of nodes in the bottleneck layer K speciﬁes the dimensionality of the nonlinear projection. We empirically determine the di- mensionality of the intrinsic manifold from the data by training D-G-K-G-D autoencoder architectures, where G is tuned via cross-validation94. An appropriate value of K is deter- mined by computing the fraction of variance explained (FVE) by the reconstructed outputs, (cid:80) (cid:80) − − SS − Q (z zˆ )2 FVE = 1 err = 1 q=1 q − q (4) SS Q (z z¯ )2 tot q=1 q q where SS is the residual sum of squares, SS is the total sum of squares, and z¯ is the err tot mean input vector. The emergence of a plateau or knee in the FVE curve at a particular value of K indicates that the predominance of variance in the data exists within a K-dimensional intrinsic manifold. We determine the location of the knee in an automated fashion using (cid:28) the L-method of Salvador and Chan98. For K D and a high FVE in excess of 70%, we R assert that the autoencoder has discovered that the high-dimensional data in D admits a R low-dimensional representation in K from which the original data can be approximately 10 ##LTLine## ##LTLine##

label: equation

text: Q

text: Q

text: E

text: z

text: zˆ

text: λ

text: w(i)

text: z

text: (Θ

text: Θ

text: )z

text: λ

text: w(i)

text: q

text: q

text: i

text: jk

text: q

text: rec

text: proj

text: q

text: i

text: jk

text: i,j,k

text: i,j,k

text: The

text: ﬁrst

text: term

text: is

text: the

text: reconstruction

text: error,

text: and

text: the

text: second

text: a

text: regularizing

text: penalty

text: known

text: as

text: weight

text: decay

text: that

text: stabilizes

text: ﬁtting

text: by

text: controlling

text: the

text: growth

text: of

text: the

text: network

text: In

text: this

text: work,

text: we

text: ﬁnd

text: our

text: ﬁtting

text: procedure

text: to

text: be

text: stable

text: in

text: the

text: absence

text: of

text: weight

text: decay,

text: and

text: choose

text: to

text: set

text: λ

text: for

text: all

text: layers.

text: Minimization

text: of

text: E

text: is

text: performed

text: using

text: the

text: backpropagation

text: i

text: algorithm

text: that

text: employs

text: gradient

text: descent

text: to

text: propagate

text: errors

text: in

text: the

text: output

text: back

text: through

text: the

text: network

text: and

text: iteratively

text: tune

text: the

text: network

text: In

text: this

text: work,

text: our

text: training

text: is

text: per-

text: formed

text: by

text: mini-batch

text: stochastic

text: gradient

text: descent

text: with

text: To

text: avoid

text: overﬁtting,

text: we

text: randomly

text: pick

text: of

text: data

text: as

text: the

text: training

text: set,

text: and

text: remaining

text: as

text: the

text: validation

text: set.

text: Training

text: is

text: terminated

text: when

text: either

text: we

text: reach

text: maximum

text: number

text: of

text: training

text: epochs,

text: or

text: the

text: validation

text: error

text: no

text: longer

text: decreases

text: for

text: a

text: continuous

text: epochs

text: (i.e.,

text: early

text: stopping).

text: Dimensionality

text: determination.

text: The

text: number

text: of

text: nodes

text: in

text: the

text: bottleneck

text: layer

text: K

text: speciﬁes

text: the

text: dimensionality

text: of

text: the

text: nonlinear

text: projection.

text: We

text: empirically

text: determine

text: the

text: di-

text: mensionality

text: of

text: the

text: intrinsic

text: manifold

text: from

text: the

text: data

text: by

text: training

text: D-G-K-G-D

text: autoencoder

text: architectures,

text: where

text: G

text: is

text: tuned

text: via

text: An

text: appropriate

text: value

text: of

text: K

text: is

text: deter-

text: mined

text: by

text: computing

text: the

text: fraction

text: of

text: variance

text: explained

text: (FVE)

text: by

text: the

text: reconstructed

text: outputs,

text: SS

text: Q

text: (z

text: zˆ

text: FVE

text: err

text: q

text: q

text: SS

text: Q

text: (z

text: z¯

text: tot

text: q

text: q

text: where

text: SS

text: is

text: the

text: residual

text: sum

text: of

text: squares,

text: SS

text: is

text: the

text: total

text: sum

text: of

text: squares,

text: and

text: z¯

text: is

text: the

text: err

text: tot

text: mean

text: input

text: vector.

text: The

text: emergence

text: of

text: a

text: plateau

text: or

text: knee

text: in

text: the

text: FVE

text: curve

text: at

text: a

text: particular

text: value

text: of

text: K

text: indicates

text: that

text: the

text: predominance

text: of

text: variance

text: in

text: the

text: data

text: exists

text: within

text: a

text: K-dimensional

text: intrinsic

text: manifold.

text: We

text: determine

text: the

text: location

text: of

text: the

text: knee

text: in

text: an

text: automated

text: fashion

text: using

text: the

text: L-method

text: of

text: Salvador

text: and

text: For

text: K

text: D

text: and

text: a

text: high

text: FVE

text: in

text: excess

text: of

text: we

text: R

text: assert

text: that

text: the

text: autoencoder

text: has

text: discovered

text: that

text: the

text: high-dimensional

text: data

text: in

text: D

text: admits

text: a

text: R

text: low-dimensional

text: representation

text: in

text: K

text: from

text: which

text: the

text: original

text: data

text: can

text: be

text: approximately

text: ##LTLine##

text: ##LTLine##


text: R DYNAMICS FOR A CLASS OF POLYNOMIAL MAPS IN 2 11 (cid:26) ∈ | | | | | | | | × f) If (x, y) U( c k a 4, c k a 4), U = [c, a ] [c, a ], then 1 1 1 1 − | | | | ≤ ≤ a c k a 4 x a ⇒ ≤ − ≤ | | | | | | | | 1 − | | | 1| ≤ ≤ 1 = 0 xy a2 2 c k a 5 + c 2k a 8, a c k a 4 y a 1 1 1 1 1 1 | | | | | | | | ⊂ | | | | | | | | | | | | i.e. f(U( c k a 4, c k a 4)) R(2 c k a 5 + c 2k a 8, c k a 4). 1 1 1 1 1 Hence, we have that fnk+1(z) is in one of the following sets: | | | | | | | | − | | | | | | | | | | | | − | | | | 1) R( c k a 5 + c k a 6 c 2k a 8, c k a 4 + c k a 5 c 2k a 7); | | | 1| | | |1 | − | | |1 | | |1 | | | |1 | | − |1| | | 2) R( c k a 5 + 2 c k a 6 c 2k a 8 + c 2k a 9 + c 2k a 10 c 3k a 12, | | | | 1 1 1 1 1 1 c k a 5); 1 | | | | | | | | 3) R( c k a 5, c k a 4); | | |1 | | |1 | | | | | | 4) R(2 c k a 5 + c 2k a 8, c k a 4). (cid:48) 1 1 1 If R is the union of the sets in 1), 2), 3) and 4), then it is not hard to (cid:48) ⊂ | | | | | | | | (cid:3) prove that R R( c k+1 a 3, c k+1 a 3) and we are done. 1 1 ⊂ Deﬁnition 2.10. Let Z , Z , Z , Z , Z R be the sets deﬁned by (see 0 1 2 3 4 Figure 5) | | | | Z = R( a 3, a 3), 0 1 | 1| × − | | Z = Z ]a + a 2, 0] [a a 2, a ], 1 1 1 | 1| | 1 | ×1 −1 | | − | | Z = Z [a + a 3, a + a 2] [a a 2, a a 3], 2 2 1 1 | |1 × 1 − | |1 −1 | |1 1 Z = Z [a , a + a 3] [a a 2, a a 3] and 3 3 1 1| | 1 | 1| × 1 −1| | 1 Z = Z [a + a 3, a + a 2] [a a 3, a ]. 4 4 1 1 1 1 1 1 1 Figure 5. The sets Z , Z , Z , Z , Z . 0 1 2 3 4 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: R

text: DYNAMICS

text: FOR

text: A

text: CLASS

text: OF

text: POLYNOMIAL

text: MAPS

text: IN

text: f)

text: If

text: (x,

text: y)

text: U(

text: c

text: k

text: a

text: c

text: k

text: a

text: U

text: [c,

text: a

text: [c,

text: a

text: then

text: a

text: c

text: k

text: a

text: x

text: a

text: xy

text: c

text: k

text: a

text: c

text: a

text: a

text: c

text: k

text: a

text: y

text: a

text: i.e.

text: f(U(

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: a

text: c

text: k

text: a

text: Hence,

text: we

text: have

text: that

text: is

text: in

text: one

text: of

text: the

text: following

text: sets:

text: R(

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: a

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: a

text: R(

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: a

text: c

text: a

text: c

text: a

text: c

text: a

text: c

text: k

text: a

text: R(

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: k

text: a

text: c

text: a

text: c

text: k

text: a

text: If

text: R

text: is

text: the

text: union

text: of

text: the

text: sets

text: in

text: and

text: then

text: it

text: is

text: not

text: hard

text: to

text: prove

text: that

text: R

text: R(

text: c

text: a

text: c

text: a

text: and

text: we

text: are

text: done.

text: Deﬁnition

text: Let

text: Z

text: Z

text: Z

text: Z

text: Z

text: R

text: be

text: the

text: sets

text: deﬁned

text: by

text: (see

text: Figure

text: Z

text: R(

text: a

text: a

text: Z

text: Z

text: ]a

text: a

text: [a

text: a

text: a

text: ×1

text: −1

text: Z

text: Z

text: [a

text: a

text: a

text: a

text: [a

text: a

text: a

text: a

text: −1

text: Z

text: Z

text: [a

text: a

text: a

text: [a

text: a

text: a

text: a

text: and

text: Z

text: Z

text: [a

text: a

text: a

text: a

text: [a

text: a

text: a

text: Figure

text: The

text: sets

text: Z

text: Z

text: Z

text: Z

text: Z

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: R DYNAMICS FOR A CLASS OF POLYNOMIAL MAPS IN 2 13 × − −→ T [a + a3 + a4 + a5, a ] [a a3, a + a2] f 1 1 1 1 1 1 1 1 1 − − × −→ U[a + a3, a + a5 a7 a8] [a + a3 + a4 + a5, a ] f − 1− 1 1 1 1 1 1 1× 1 1 1 − − R[a + a6 a8 a9, a + 2a4 + a5 + 2a6 + a7 + a8] [a + a3, a + a5 a7 a8] 1 1 1 1 1 1 1 ⊂ 1∪ 1 1 1 1 1 1 1 1 Z Z . 0 4 ∈ ∈ ∪ ∪ (cid:3) Therefore, if z Z2 then fn1(z) Z0 Z3 Z4. − ≤ − ∈ ∈ ∪ Lemma 2.13. Let 1 < c 34. If z Z3, then fn1(z) Z0 Z4. − × − Proof. We have that Z = Z [a , a a3] [a a2, a + a3]. Thus, 3 3 1 1 1 1 1 1 1 −→ − × − ∪ − × − Z f T [a a6, a ] [a , a a3] S[a , a a3] [a , a a3]. 3 1 1 1 1 1 1 1 1 1 1 1 1 Furthermore, − × − −→ − × − −→ S[a , a a3] [a , a a3] f T [a 2a4 + a6, a ] [a , a a3] f −1 1 ×1 − 1 1 1 ∪ 1 −1 1 1 × 1 −1 1 U[a a4, a ] [a 2a4 + a6, a ] R[a , a 2a5 + a7] [a 2a4 + a6, a ] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 and − × − −→ − − × − U[a a4, a ] [a 2a4+a6, a ] f R[a , a 3a5+a7+2a8 a10] [a a4, a ]. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 On the other hand, − × − −→ T [a a6, a ] [a , a a3] f − × 1− 1 1∪ 1 1 − 1 × − U[a a4, a ] [a a6, a ] R[a , a a7] [a a6, a ] and 1 1 1 1 1 1 1 1 1 1 1 1 − × − −→ − − × − U[a a4, a ] [a a6, a ] f R[a , a a5 a7 + a10] [a a4, a ]. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ∈ Hence, if z − Z3 then f×n1(z)−in one of the fo⊂llowing sets: a) R[a , a 2a5 + a7] [a 2a4 + a6, a ] Z ; 1 1 − 1 1 1− 1 × 1 −1 0 ⊂ ∪ b) R[a , a 3a5 + a7 + 2a8 a10] [a a4, a ] (Z Z ); 1 1 − 1× 1 − 1 ⊂1 1 1 1 0 4 c) R[a , a a7] [a a6, a ] Z ; 1 1 − 1 − 1 1 ×1 −0 ⊂ d) R[a , a a5 a7 + a10] [a a4, a ] Z . 1 1 1∈ 1 1 1∈ 1\ 1 ∪ 0 (cid:3) Therefore, if z Z3 then fn1(z) R Z0 Z4. − ≤ − ∈ ≥ Lemma 2.14. Let 1 < c 3. If z Z , then there exists j 1 such ∈ 4 4 that fnj(z) Z0. ∈ | | | | × − | | Proof. Let z Z = Z [a + a 3, a + a 2] [a a 3, a ]. Hence, there | | ≤ 4≤ | 4| 1 1 1 ∈ 1 − 1 1 1× exists a 3 ε a 2 such that z Z [a a3, a + ε ] [a + a3, a ]. 1 0 1 4 1 1 1 0 1 1 1 Thus, we have that ∈ − × − f(z) T [a + a ε , a a6] [a a3, a + ε ], 1 1 0 1 1 1 1 1 0 ##LTLine## ##LTLine##

text: R

text: DYNAMICS

text: FOR

text: A

text: CLASS

text: OF

text: POLYNOMIAL

text: MAPS

text: IN

text: T

text: [a

text: a

text: [a

text: a

text: f

text: U[a

text: a

text: [a

text: a

text: f

text: 1−

text: 1×

text: R[a

text: a

text: [a

text: a

text: 1∪

text: Z

text: Z

text: Therefore,

text: if

text: z

text: then

text: Lemma

text: Let

text: c

text: If

text: z

text: then

text: Proof.

text: We

text: have

text: that

text: Z

text: Z

text: [a

text: a

text: [a

text: a

text: Thus,

text: Z

text: f

text: T

text: [a

text: a

text: [a

text: a

text: S[a

text: a

text: [a

text: a

text: Furthermore,

text: S[a

text: a

text: [a

text: a

text: f

text: T

text: [a

text: a

text: [a

text: a

text: f

text: −1

text: ×1

text: −1

text: −1

text: U[a

text: a

text: [a

text: a

text: R[a

text: a

text: [a

text: a

text: and

text: U[a

text: a

text: [a

text: a

text: f

text: R[a

text: a

text: [a

text: a

text: On

text: the

text: other

text: hand,

text: T

text: [a

text: a

text: [a

text: a

text: f

text: 1−

text: 1∪

text: U[a

text: a

text: [a

text: a

text: R[a

text: a

text: [a

text: a

text: and

text: U[a

text: a

text: [a

text: a

text: f

text: R[a

text: a

text: [a

text: a

text: Hence,

text: if

text: z

text: then

text: one

text: of

text: the

text: fo⊂llowing

text: sets:

text: a)

text: R[a

text: a

text: [a

text: a

text: Z

text: 1−

text: −1

text: b)

text: R[a

text: a

text: [a

text: a

text: (Z

text: Z

text: 1×

text: ⊂1

text: c)

text: R[a

text: a

text: [a

text: a

text: Z

text: ×1

text: −0

text: d)

text: R[a

text: a

text: [a

text: a

text: Z

text: 1∈

text: 1∈

text: Therefore,

text: if

text: z

text: then

text: R

text: Lemma

text: Let

text: c

text: If

text: z

text: Z

text: then

text: there

text: exists

text: j

text: such

text: that

text: fnj(z)

text: Proof.

text: Let

text: z

text: Z

text: Z

text: [a

text: a

text: a

text: a

text: [a

text: a

text: a

text: Hence,

text: there

text: 4≤

text: 1×

text: exists

text: a

text: ε

text: a

text: such

text: that

text: z

text: Z

text: [a

text: a

text: ε

text: [a

text: a

text: Thus,

text: we

text: have

text: that

text: f(z)

text: T

text: [a

text: a

text: ε

text: a

text: [a

text: a

text: ε

text: ##LTLine##

text: ##LTLine##


text: 16 DANILO ANTONIO CAPRIO { } Let z = max x , y < a and deﬁne the sequence z = z2 + c and 0 0 0 2 ≥ 1 0 z = z − z − + c, for all integer n 2. Thus, we have that n n 1 n 2 ≤ ≤ ≤ ≤ 1 + c x z < a , 0 y z < a , ≤ ≤0 0 2 ≤0 ≤0 2 1 + c x z2 + c = z , 0 y z < a , ≤1 ≤0 1 1≤ 0≤ 2 1 + c x z z + c = z , 0 y z , 2 0 1 2 2 1 . . . ≤ ≤ ≤ ≤ 1 + c x z , 0 y z − , n n n n 1 ≥ ≥ ∈ N for all integer n 1. Observe that z 1+c > 0, for all n . Furthermore, n ≤ ⇒ ≤ ⇒ 0 < 1 + c z < a = 0 < 1 + c z = z2 + c < z < a = 0≤ 2 1 0 0 ⇒2 0 < 1 + c z = z z + c < z2 + c = z < z < a = ≤ 2 1 0 0 1 0 2 ⇒ ⇒ 0 < 1 + c z = z z + c < z z + c = z < z < z < a = . . . = ≤ 3 2 1 1 0 2 1 0 2 0 < 1 + c z < z − < . . . < z < z < a , for all positive integer n. n n 1 1 0 2 Therefore, (z ) is a decreasing positive sequence, which converges for ∈ n n some l [1 + c, a [. Since z = z − z − + c, it follows that l = l2 + c, i.e. ∈ { } 2 n n≤1 n 2 l a , a . Since a < 0 < 1 + c l < z < a , it is absurd. 1 2 1 ∈ N 0 2 ∈ Therefore, there exists N such that fN(z) / H . ≤ 1 Case 2: x = a and 0 y < a . 0 2 0 2 In this case, x = a y +c < a2 +c = a , y = a , x = x a +c < a2 +c = 1 2 0 2 2 1 2 2 1 2 2 a and y < a . 2 2 ∈2 If (x , y ) H , then we are done from Case 1. 2 2 ∈ 1 If (x , y ) / H , then the result is valid for N = 2. 2 2 ≤1 Case 3: 1 + c x < a and y = a . 0 2 0 2 In this case x = x a + c < a2 + c = a and y < a . ∈ 1 0 2 2 2 1 2 If (x , y ) H , then we are done from Case 1. 1 1 ∈ 1 (cid:3) If (x , y ) / H , then the result is valid for N = 1. 1 1 1 Remark 2. From Lemmas 2.2 and 2.15 and from Proposition 1, we have ∈ ∪ ∈ ∪ R \ ∪ ⊂ that if f(z) A H , then z A H . Furthermore, f( 2 (A H )) R \ ∪ 2 2 2 2 (A H ). Thus, from Propositions 1, 8 and 9 and from Lemma 2.2, it 2 ∪ follows that A H = W s((a , a )). H A 2 2 In this subsection, we will prove Proposition 4. H ∪ ∪ ∪ ∪ ∪ Denote by = R R R (cid:83) R A H . 0 1 2 3 H A K \ ∞ − H ∪ ∪ Proposition 10. If V := + + f n( ), then V = W s(p) W s(f(p)) n=0 W s(f2(p)).

text: DANILO

text: ANTONIO

text: CAPRIO

text: Let

text: z

text: max

text: x

text: y

text: a

text: and

text: deﬁne

text: the

text: sequence

text: z

text: c

text: and

text: z

text: z

text: z

text: c,

text: for

text: all

text: integer

text: n

text: Thus,

text: we

text: have

text: that

text: n

text: n

text: n

text: c

text: x

text: z

text: a

text: y

text: z

text: a

text: ≤0

text: ≤0

text: ≤0

text: c

text: x

text: c

text: z

text: y

text: z

text: a

text: ≤1

text: ≤0

text: 1≤

text: 0≤

text: c

text: x

text: z

text: z

text: c

text: z

text: y

text: z

text: c

text: x

text: z

text: y

text: z

text: n

text: n

text: n

text: n

text: N

text: for

text: all

text: integer

text: n

text: Observe

text: that

text: z

text: for

text: all

text: n

text: Furthermore,

text: n

text: c

text: z

text: a

text: c

text: z

text: c

text: z

text: a

text: 0≤

text: ⇒2

text: c

text: z

text: z

text: z

text: c

text: c

text: z

text: z

text: a

text: c

text: z

text: z

text: z

text: c

text: z

text: z

text: c

text: z

text: z

text: z

text: a

text: c

text: z

text: z

text: z

text: z

text: a

text: for

text: all

text: positive

text: integer

text: n.

text: n

text: n

text: Therefore,

text: (z

text: is

text: a

text: decreasing

text: positive

text: sequence,

text: which

text: converges

text: for

text: n

text: n

text: some

text: l

text: c,

text: a

text: Since

text: z

text: z

text: z

text: c,

text: it

text: follows

text: that

text: l

text: c,

text: i.e.

text: n

text: n

text: l

text: a

text: a

text: Since

text: a

text: c

text: l

text: z

text: a

text: it

text: is

text: absurd.

text: N

text: Therefore,

text: there

text: exists

text: N

text: such

text: that

text: fN(z)

text: H

text: Case

text: x

text: a

text: and

text: y

text: a

text: In

text: this

text: case,

text: x

text: a

text: y

text: +c

text: +c

text: a

text: y

text: a

text: x

text: x

text: a

text: +c

text: +c

text: a

text: and

text: y

text: a

text: ∈2

text: If

text: (x

text: y

text: H

text: then

text: we

text: are

text: done

text: from

text: Case

text: If

text: (x

text: y

text: H

text: then

text: the

text: result

text: is

text: valid

text: for

text: N

text: ≤1

text: Case

text: c

text: x

text: a

text: and

text: y

text: a

text: In

text: this

text: case

text: x

text: x

text: a

text: c

text: c

text: a

text: and

text: y

text: a

text: If

text: (x

text: y

text: H

text: then

text: we

text: are

text: done

text: from

text: Case

text: If

text: (x

text: y

text: H

text: then

text: the

text: result

text: is

text: valid

text: for

text: N

text: Remark

text: From

text: Lemmas

text: and

text: and

text: from

text: Proposition

text: we

text: have

text: R

text: that

text: if

text: f(z)

text: A

text: H

text: then

text: z

text: A

text: H

text: Furthermore,

text: f(

text: (A

text: H

text: R

text: (A

text: H

text: Thus,

text: from

text: Propositions

text: and

text: and

text: from

text: Lemma

text: it

text: follows

text: that

text: A

text: H

text: W

text: s((a

text: a

text: H

text: A

text: In

text: this

text: subsection,

text: we

text: will

text: prove

text: Proposition

text: H

text: Denote

text: by

text: R

text: R

text: R

text: R

text: A

text: H

text: H

text: A

text: K

text: H

text: Proposition

text: If

text: V

text: f

text: n(

text: then

text: V

text: W

text: s(p)

text: W

text: s(f(p))

text: W


text: R DYNAMICS FOR A CLASS OF POLYNOMIAL MAPS IN 2 3 K − − Figure 1. The set + in the cases: a) c = 0.8, b) c = 1, − c) c = 2.1. ≤ − − − − only if c 1. Also, p = ( 1, 1), f(p) = (1 + c, 1) and f2(p) = ( 1, 1 + c) 4− is the only 3 cycle of f. Furthermore, the following properties are valid: a) if c < 1, then θ is a saddle ﬁxed point of f; − 4 b) if 2 < c < 1, then α is an attracting ﬁxed point of f; − 4 (cid:0) (cid:1) ± 2πi c) if c = −2, then α is an indiﬀerent ﬁxed point of f with eigenvalues e 3 ; d) if c < 2, then α is a repelling ﬁxed point of f; e) if c = 1, then α = θ = 1, 1 and the corresponding eigenvalues are 1 and − 4 2 2 1. 2 The reader can check the proof of theses facts in [2] (Proposition 3.1). − − When c = 0, we have that α = (0, 0), θ = (1, 1), p = ( 1, 1), f(p) = − − K (1, 1) and f2(p) = ( 1, 1). In Figure 2 we can see + (when c = 0), where K W s(α) is the gray region, i.e. W s(α) = int( +), W s(θ) is the curve which ∪ ∪ contains the point θ and W s(p) W s(f(p)) W s(f2(p)) are the curves which contains the points p, f(p) and f2(p). Figure 2. Case c = 0. In this section, we will concentrate on proving the following theorem. − K ∪ ∪ ∪ Theorem 2.1. If 1 < c < 0, then + = W s(α) W s(θ) W s(p) ∪ − − W s(f(p)) W s(f2(p)), where p = ( 1, 1), α = (a , a ) and θ = (a , a ). 1 1 2 2 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: R

text: DYNAMICS

text: FOR

text: A

text: CLASS

text: OF

text: POLYNOMIAL

text: MAPS

text: IN

text: K

text: Figure

text: The

text: set

text: in

text: the

text: cases:

text: a)

text: c

text: b)

text: c

text: c)

text: c

text: only

text: if

text: c

text: Also,

text: p

text: f(p)

text: c,

text: and

text: c)

text: 4−

text: is

text: the

text: only

text: cycle

text: of

text: f.

text: Furthermore,

text: the

text: following

text: properties

text: are

text: valid:

text: a)

text: if

text: c

text: then

text: θ

text: is

text: a

text: saddle

text: ﬁxed

text: point

text: of

text: f;

text: b)

text: if

text: c

text: then

text: α

text: is

text: an

text: attracting

text: ﬁxed

text: point

text: of

text: f;

text: c)

text: if

text: c

text: then

text: α

text: is

text: an

text: indiﬀerent

text: ﬁxed

text: point

text: of

text: f

text: with

text: eigenvalues

text: e

text: d)

text: if

text: c

text: then

text: α

text: is

text: a

text: repelling

text: ﬁxed

text: point

text: of

text: f;

text: e)

text: if

text: c

text: then

text: α

text: θ

text: and

text: the

text: corresponding

text: eigenvalues

text: are

text: and

text: The

text: reader

text: can

text: check

text: the

text: proof

text: of

text: theses

text: facts

text: in

text: (Proposition

text: When

text: c

text: we

text: have

text: that

text: α

text: θ

text: p

text: f(p)

text: K

text: and

text: In

text: Figure

text: we

text: can

text: see

text: (when

text: c

text: where

text: K

text: W

text: s(α)

text: is

text: the

text: gray

text: region,

text: i.e.

text: W

text: s(α)

text: int(

text: W

text: s(θ)

text: is

text: the

text: curve

text: which

text: contains

text: the

text: point

text: θ

text: and

text: W

text: s(p)

text: W

text: s(f(p))

text: W

text: are

text: the

text: curves

text: which

text: contains

text: the

text: points

text: p,

text: f(p)

text: and

text: Figure

text: Case

text: c

text: In

text: this

text: section,

text: we

text: will

text: concentrate

text: on

text: proving

text: the

text: following

text: theorem.

text: K

text: Theorem

text: If

text: c

text: then

text: W

text: s(α)

text: W

text: s(θ)

text: W

text: s(p)

text: W

text: s(f(p))

text: W

text: where

text: p

text: α

text: (a

text: a

text: and

text: θ

text: (a

text: a

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##