text: and broadcast. They developed randomized Las Vegas algorithm to achieve this in the model of separate messages. Networks are assumed to be symmetric and nodes know their neighborhood. Their algorithm begins with preprocessing. First a leader is elected, by resorting to the algorithm described in Subsection , then a BFS tree is found, rooted at the leader. The expected time of O preprocessing is ((n + D log n) log ∆). The protocol itself consists of two phases: during the ﬁrst Collection phase all the messages are collected at the root, then the Distribution phase follows, during which the messages are sent from the root towards their destinations. The idea is to send messages to the root of the BFS tree and then to the target nodes along the edges of the tree, pipelining messages along the branches of the BFS tree. A deterministic local acknowledgement is used, which immediately conﬁrms a successful receipt of a message along an edge. A probabilistic analysis is done by interpreting the system as a line of queues, each with Bernoulli service and arrival times (see [22] for an alternative approach to similar problems). A set of k point-to-point transmissions O require the expected time ((k + D) log ∆). Similarly, k broadcasts require the expected time O ((k + D) log ∆ log n). The broadcasting algorithm presented in Subsection is Monte Carlo, but it may be converted to be Las Vegas, as was shown in [13]. The method is as follows. Since the size n is known, choose (cid:15) = 1/n and build a BFS tree. After the tree is expected to have been completed, collect the information along its edges from all the nodes in the tree by the procedure Collection discussed in the preceding paragraph. This is done within a certain time interval, and if not successful, then the whole algorithm is repeated from the very beginning. (cid:112) A method to obtain a gossiping algorithm from one performing broadcasting was developed O in [26]. If the broadcasting algorithm works in time (B(n)) then the resulting gossiping algorithm O operates in time ( B(n)n log n). Applying this method with the broadcasting algorithm from [26] O with B(n) = n log2 n yields a gossiping algorithm working in time (n3/2 log2 n). Similarly, the constructive algorithm from [25] with B(n) = n3/2 gives a deterministic constructive gossiping O algorithm working in time (n7/4 log n). A randomized Las-Vegas gossiping algorithm, working in O the expected time (n log4 n) was given in [27]. 6.2 Simulations Bar-Yehuda, Goldreich and Itai [11] developed a simulation of the multiple access channel with ternary feedback on the multi-hop radio network without collision detection. The simulation algorithm uses the procedures Decay and Broadcast presented in Subsection . The slowdown of O the simulation is B = ((D + log(n/(cid:15))) log ∆), that is, B is the time it takes to perform a (cid:15) (cid:15) − single broadcast of the channel on the packet network, with the probability at least 1 (cid:15), which is also the probability of correctness of the protocol. Additionally, an implementation of conﬂict- detection mechanism was developed for a multi-hop radio network without conﬂict detection, in O − time (log(1/(cid:15)) log ∆) for one step, and with the probability 1 (cid:15). It was also shown that any O broadcast-channel algorithm operating in t steps can be emulated in time (t(log t log ∆+B )) on a − O(cid:15) packet-network, with the probability 1 (cid:15). The main application is leader election in time ((D + log(n/(cid:15))) log ∆ log log n), obtained by a combination of the simulation and Willard’s algorithms, optimality of this algorithm is an open problem. Alon, Bar-Noy, Linial and Peleg [9] developed step-by-step simulations of message-passing net- works on packet radio networks. Two models were considered. In the general model a node may send in one round arbitrary distinct messages, and in the uniform model only copies of one message. 30 ##LTLine##

text: and

text: broadcast.

text: They

text: developed

text: randomized

text: Las

text: Vegas

text: algorithm

text: to

text: achieve

text: this

text: in

text: the

text: model

text: of

text: separate

text: messages.

text: Networks

text: are

text: assumed

text: to

text: be

text: symmetric

text: and

text: nodes

text: know

text: their

text: neighborhood.

text: Their

text: algorithm

text: begins

text: with

text: preprocessing.

text: First

text: a

text: leader

text: is

text: elected,

text: by

text: resorting

text: to

text: the

text: algorithm

text: described

text: in

text: Subsection

text: then

text: a

text: BFS

text: tree

text: is

text: found,

text: rooted

text: at

text: the

text: leader.

text: The

text: expected

text: time

text: of

text: O

text: preprocessing

text: is

text: ((n

text: D

text: log

text: n)

text: log

text: The

text: protocol

text: itself

text: consists

text: of

text: two

text: phases:

text: during

text: the

text: ﬁrst

text: Collection

text: phase

text: all

text: the

text: messages

text: are

text: collected

text: at

text: the

text: root,

text: then

text: the

text: Distribution

text: phase

text: follows,

text: during

text: which

text: the

text: messages

text: are

text: sent

text: from

text: the

text: root

text: towards

text: their

text: destinations.

text: The

text: idea

text: is

text: to

text: send

text: messages

text: to

text: the

text: root

text: of

text: the

text: BFS

text: tree

text: and

text: then

text: to

text: the

text: target

text: nodes

text: along

text: the

text: edges

text: of

text: the

text: tree,

text: pipelining

text: messages

text: along

text: the

text: branches

text: of

text: the

text: BFS

text: tree.

text: A

text: deterministic

text: local

text: acknowledgement

text: is

text: used,

text: which

text: immediately

text: conﬁrms

text: a

text: successful

text: receipt

text: of

text: a

text: message

text: along

text: an

text: edge.

text: A

text: probabilistic

text: analysis

text: is

text: done

text: by

text: interpreting

text: the

text: system

text: as

text: a

text: line

text: of

text: queues,

text: each

text: with

text: Bernoulli

text: service

text: and

text: arrival

text: times

text: (see

text: for

text: an

text: alternative

text: approach

text: to

text: similar

text: problems).

text: A

text: set

text: of

text: k

text: point-to-point

text: transmissions

text: O

text: require

text: the

text: expected

text: time

text: ((k

text: D)

text: log

text: Similarly,

text: k

text: broadcasts

text: require

text: the

text: expected

text: time

text: O

text: ((k

text: D)

text: log

text: log

text: n).

text: The

text: broadcasting

text: algorithm

text: presented

text: in

text: Subsection

text: is

text: Monte

text: Carlo,

text: but

text: it

text: may

text: be

text: converted

text: to

text: be

text: Las

text: Vegas,

text: as

text: was

text: shown

text: in

text: The

text: method

text: is

text: as

text: follows.

text: Since

text: the

text: size

text: n

text: is

text: known,

text: choose

text: and

text: build

text: a

text: BFS

text: tree.

text: After

text: the

text: tree

text: is

text: expected

text: to

text: have

text: been

text: completed,

text: collect

text: the

text: information

text: along

text: its

text: edges

text: from

text: all

text: the

text: nodes

text: in

text: the

text: tree

text: by

text: the

text: procedure

text: Collection

text: discussed

text: in

text: the

text: preceding

text: paragraph.

text: This

text: is

text: done

text: within

text: a

text: certain

text: time

text: interval,

text: and

text: if

text: not

text: successful,

text: then

text: the

text: whole

text: algorithm

text: is

text: repeated

text: from

text: the

text: very

text: beginning.

text: A

text: method

text: to

text: obtain

text: a

text: gossiping

text: algorithm

text: from

text: one

text: performing

text: broadcasting

text: was

text: developed

text: O

text: in

text: If

text: the

text: broadcasting

text: algorithm

text: works

text: in

text: time

text: (B(n))

text: then

text: the

text: resulting

text: gossiping

text: algorithm

text: O

text: operates

text: in

text: time

text: B(n)n

text: log

text: n).

text: Applying

text: this

text: method

text: with

text: the

text: broadcasting

text: algorithm

text: from

text: O

text: with

text: B(n)

text: n

text: n

text: yields

text: a

text: gossiping

text: algorithm

text: working

text: in

text: time

text: n).

text: Similarly,

text: the

text: constructive

text: algorithm

text: from

text: with

text: B(n)

text: gives

text: a

text: deterministic

text: constructive

text: gossiping

text: O

text: algorithm

text: working

text: in

text: time

text: log

text: n).

text: A

text: randomized

text: Las-Vegas

text: gossiping

text: algorithm,

text: working

text: in

text: O

text: the

text: expected

text: time

text: (n

text: n)

text: was

text: given

text: in

text: Simulations

text: Bar-Yehuda,

text: Goldreich

text: and

text: Itai

text: developed

text: a

text: simulation

text: of

text: the

text: multiple

text: access

text: channel

text: with

text: ternary

text: feedback

text: on

text: the

text: multi-hop

text: radio

text: network

text: without

text: collision

text: detection.

text: The

text: simulation

text: algorithm

text: uses

text: the

text: procedures

text: Decay

text: and

text: Broadcast

text: presented

text: in

text: Subsection

text: The

text: slowdown

text: of

text: O

text: the

text: simulation

text: is

text: B

text: ((D

text: log

text: that

text: is,

text: B

text: is

text: the

text: time

text: it

text: takes

text: to

text: perform

text: a

text: single

text: broadcast

text: of

text: the

text: channel

text: on

text: the

text: packet

text: network,

text: with

text: the

text: probability

text: at

text: least

text: which

text: is

text: also

text: the

text: probability

text: of

text: correctness

text: of

text: the

text: protocol.

text: Additionally,

text: an

text: implementation

text: of

text: conﬂict-

text: detection

text: mechanism

text: was

text: developed

text: for

text: a

text: multi-hop

text: radio

text: network

text: without

text: conﬂict

text: detection,

text: in

text: O

text: time

text: log

text: for

text: one

text: step,

text: and

text: with

text: the

text: probability

text: It

text: was

text: also

text: shown

text: that

text: any

text: O

text: broadcast-channel

text: algorithm

text: operating

text: in

text: t

text: steps

text: can

text: be

text: emulated

text: in

text: time

text: (t(log

text: t

text: log

text: ∆+B

text: on

text: a

text: packet-network,

text: with

text: the

text: probability

text: The

text: main

text: application

text: is

text: leader

text: election

text: in

text: time

text: ((D

text: log

text: log

text: log

text: n),

text: obtained

text: by

text: a

text: combination

text: of

text: the

text: simulation

text: and

text: Willard’s

text: algorithms,

text: optimality

text: of

text: this

text: algorithm

text: is

text: an

text: open

text: problem.

text: Alon,

text: Bar-Noy,

text: Linial

text: and

text: Peleg

text: developed

text: step-by-step

text: simulations

text: of

text: message-passing

text: net-

text: works

text: on

text: packet

text: radio

text: networks.

text: Two

text: models

text: were

text: considered.

text: In

text: the

text: general

text: model

text: a

text: node

text: may

text: send

text: in

text: one

text: round

text: arbitrary

text: distinct

text: messages,

text: and

text: in

text: the

text: uniform

text: model

text: only

text: copies

text: of

text: one

text: message.

text: ##LTLine##


text: into layers in such a way that two consecutive layers induce a complete binary graph, and there are no other edges except for those connecting any two nodes in consecutive layers. The number D of layers is the depth, and the lemma is applied to each layer of size n/D. 7 Related work In this section we present additional relevant results concerning communication algorithms in radio networks. Ga¸sieniec, Pelc and Peleg [45] compared the locally and globally synchronous models of single- hop radio networks in the context of the wakeup problem, in which the time when each station joins the protocol is controlled by an adversary, and the goal of an algorithm is to perform a successful broadcast as soon as possible. If the stations have access to a global clock then wakeup can be O − realized in time (log n log(1/(cid:15))) with the probability at least 1 (cid:15), by iterating procedure Decay. If the local clocks are not synchronized, then processors may ﬂip coins with the probability 1/n of heads to come up, to decide if to transmit in a step, this yields an algorithm operating in time O − (n log(1/(cid:15))) with the probability at least 1 (cid:15). Deterministic algorithms in such setting require O time Ω(n), and deterministic schedules are known to exist achieving time (n log2 n). Dynamic aspects of radio networks include not only the mobility of nodes, but also the possibility of changing the ranges of nodes by modifying their power consumption. To study such aspects, the notion of a radio network needs to be modiﬁed, for instance by assuming that the nodes are in some metric space and the reachability relation is determined by ranges that the nodes can cover. A multi-hop network is called power-controlled if hosts are able to change their transmission ranges, and in this way change also the topology of the underlying reachability graph. Adler and Scheideler [5] introduced a general formal model of power-controlled networks, in which each pair of vertices is assigned the lowest transmission power that allows to maintain a direct connection between the vertices. They developed eﬃcient strategies for permutation routing in such networks. They considered also a special case where the nodes are located in a square region in the plane, distributed randomly, and the power consumption to maintain a connection is proportional to the di√stance. They showed that permutation routing on such n-node networks can b√e performed O in ( n) steps, which was then proved to be optimal by a matching lower bound Ω( n). Diks, Kranakis, Krizanc and Pelc [33] developed deterministic algorithms and lower bounds for broadcasting in the case of nodes located on a line, the nodes know their coordinates. Ravishankar and Singh [94, 93] studied broadcasting and gossiping when stations are randomly placed on a line. Kranakis, Krizanc and Pelc [68] studied deterministic fault-tolerant broadcasting in radio networks with the stations located either on a line or on a two-dimensional grid, some of them faulty. Kushilevitz and Mansour [70] considered communication in noisy single-hop networks. The speciﬁc problem they studied is that of computing a threshold function of the bits stored in the nodes, one bit per node. The protocols are assumed to be oblivious, so the bits cannot be encoded by silence/transmission sequences. Every bit transmitted is ﬂipped randomly and independently over the receiving stations, due to noise, the probability that a wrong bit is received is below 1/2, but this probability is not assumed to be known by the stations. Let n be the number of stations. ≤ A protocol is developed which, for a given natural number k n and (cid:15) > 0, decides if the number − O of bits equal to 1 is at least k with the probability at least 1 (cid:15) by performing (n) transmissions. The following are some results on centralized oﬀ-line algorithms computing broadcast schedules, 32 ##LTLine## ##LTLine##

text: into

label: paragraph

text: layers

text: in

text: such

text: a

text: way

text: that

text: two

text: consecutive

text: layers

text: induce

text: a

text: complete

text: binary

text: graph,

text: and

text: there

text: are

text: no

text: other

text: edges

text: except

text: for

text: those

text: connecting

text: any

text: two

text: nodes

text: in

text: consecutive

text: layers.

text: The

text: number

text: D

text: of

text: layers

text: is

text: the

text: depth,

text: and

text: the

text: lemma

text: is

text: applied

text: to

text: each

text: layer

text: of

text: size

text: n/D.

label: section

text: Related

text: work

text: In

text: this

text: section

text: we

text: present

text: additional

text: relevant

text: results

text: concerning

text: communication

text: algorithms

text: in

text: radio

text: networks.

text: Ga¸sieniec,

text: Pelc

text: and

text: Peleg

text: compared

text: the

text: locally

text: and

text: globally

text: synchronous

text: models

text: of

text: single-

text: hop

text: radio

text: networks

text: in

text: the

text: context

text: of

text: the

text: wakeup

text: problem,

text: in

text: which

text: the

text: time

text: when

text: each

text: station

text: joins

text: the

text: protocol

text: is

text: controlled

text: by

text: an

text: adversary,

text: and

text: the

text: goal

text: of

text: an

text: algorithm

text: is

text: to

text: perform

text: a

text: successful

text: broadcast

text: as

text: soon

text: as

text: possible.

text: If

text: the

text: stations

text: have

text: access

text: to

text: a

text: global

text: clock

text: then

text: wakeup

text: can

text: be

text: O

text: realized

text: in

text: time

text: (log

text: n

text: with

text: the

text: probability

text: at

text: least

text: by

text: iterating

text: procedure

text: Decay.

text: If

text: the

text: local

text: clocks

text: are

text: not

text: synchronized,

text: then

text: processors

text: may

text: ﬂip

text: coins

text: with

text: the

text: probability

text: of

text: heads

text: to

text: come

text: up,

text: to

text: decide

text: if

text: to

text: transmit

text: in

text: a

text: step,

text: this

text: yields

text: an

text: algorithm

text: operating

text: in

text: time

text: O

text: (n

text: with

text: the

text: probability

text: at

text: least

text: Deterministic

text: algorithms

text: in

text: such

text: setting

text: require

text: O

text: time

text: Ω(n),

text: and

text: deterministic

text: schedules

text: are

text: known

text: to

text: exist

text: achieving

text: time

text: (n

text: n).

text: Dynamic

text: aspects

text: of

text: radio

text: networks

text: include

text: not

text: only

text: the

text: mobility

text: of

text: nodes,

text: but

text: also

text: the

text: possibility

text: of

text: changing

text: the

text: ranges

text: of

text: nodes

text: by

text: modifying

text: their

text: power

text: consumption.

text: To

text: study

text: such

text: aspects,

text: the

text: notion

text: of

text: a

text: radio

text: network

text: needs

text: to

text: be

text: modiﬁed,

text: for

text: instance

text: by

text: assuming

text: that

text: the

text: nodes

text: are

text: in

text: some

text: metric

text: space

text: and

text: the

text: reachability

text: relation

text: is

text: determined

text: by

text: ranges

text: that

text: the

text: nodes

text: can

text: cover.

text: A

text: multi-hop

text: network

text: is

text: called

text: power-controlled

text: if

text: hosts

text: are

text: able

text: to

text: change

text: their

text: transmission

text: ranges,

text: and

text: in

text: this

text: way

text: change

text: also

text: the

text: topology

text: of

text: the

text: underlying

text: reachability

text: graph.

text: Adler

text: and

text: Scheideler

text: introduced

text: a

text: general

text: formal

text: model

text: of

text: power-controlled

text: networks,

text: in

text: which

text: each

text: pair

text: of

text: vertices

text: is

text: assigned

text: the

text: lowest

text: transmission

text: power

text: that

text: allows

text: to

text: maintain

text: a

text: direct

text: connection

text: between

text: the

text: vertices.

text: They

text: developed

text: eﬃcient

text: strategies

text: for

text: permutation

text: routing

text: in

text: such

text: networks.

text: They

text: considered

text: also

text: a

text: special

text: case

text: where

text: the

text: nodes

text: are

text: located

text: in

text: a

text: square

text: region

text: in

text: the

text: plane,

text: distributed

text: randomly,

text: and

text: the

text: power

text: consumption

text: to

text: maintain

text: a

text: connection

text: is

text: proportional

text: to

text: the

text: di√stance.

text: They

text: showed

text: that

text: permutation

text: routing

text: on

text: such

text: n-node

text: networks

text: can

text: b√e

text: performed

text: O

text: in

text: n)

text: steps,

text: which

text: was

text: then

text: proved

text: to

text: be

text: optimal

text: by

text: a

text: matching

text: lower

text: bound

text: Ω(

text: n).

text: Diks,

text: Kranakis,

text: Krizanc

text: and

text: Pelc

text: developed

text: deterministic

text: algorithms

text: and

text: lower

text: bounds

text: for

text: broadcasting

text: in

text: the

text: case

text: of

text: nodes

text: located

text: on

text: a

text: line,

text: the

text: nodes

text: know

text: their

text: coordinates.

text: Ravishankar

text: and

text: Singh

text: studied

text: broadcasting

text: and

text: gossiping

text: when

text: stations

text: are

text: randomly

text: placed

text: on

text: a

text: line.

text: Kranakis,

text: Krizanc

text: and

text: Pelc

text: studied

text: deterministic

text: fault-tolerant

text: broadcasting

text: in

text: radio

text: networks

text: with

text: the

text: stations

text: located

text: either

text: on

text: a

text: line

text: or

text: on

text: a

text: two-dimensional

text: grid,

text: some

text: of

text: them

text: faulty.

text: Kushilevitz

text: and

text: Mansour

text: considered

text: communication

text: in

text: noisy

text: single-hop

text: networks.

text: The

text: speciﬁc

text: problem

text: they

text: studied

text: is

text: that

text: of

text: computing

text: a

text: threshold

text: function

text: of

text: the

text: bits

text: stored

text: in

text: the

text: nodes,

text: one

text: bit

text: per

text: node.

text: The

text: protocols

text: are

text: assumed

text: to

text: be

text: oblivious,

text: so

text: the

text: bits

text: cannot

text: be

text: encoded

text: by

text: silence/transmission

text: sequences.

text: Every

text: bit

text: transmitted

text: is

text: ﬂipped

text: randomly

text: and

text: independently

text: over

text: the

text: receiving

text: stations,

text: due

text: to

text: noise,

text: the

text: probability

text: that

text: a

text: wrong

text: bit

text: is

text: received

text: is

text: below

text: but

text: this

text: probability

text: is

text: not

text: assumed

text: to

text: be

text: known

text: by

text: the

text: stations.

text: Let

text: n

text: be

text: the

text: number

text: of

text: stations.

text: A

text: protocol

text: is

text: developed

text: which,

text: for

text: a

text: given

text: natural

text: number

text: k

text: n

text: and

text: decides

text: if

text: the

text: number

text: O

text: of

text: bits

text: equal

text: to

text: is

text: at

text: least

text: k

text: with

text: the

text: probability

text: at

text: least

text: by

text: performing

text: (n)

text: transmissions.

text: The

text: following

text: are

text: some

text: results

text: on

text: centralized

text: oﬀ-line

text: algorithms

text: computing

text: broadcast

text: schedules,

text: ##LTLine##

text: ##LTLine##


text: the networks are known then, and are inputs to such sequential algorithms. Chlamtac and We- instein [20] developed a deterministic algorithm which ﬁnds in polynomial time a schedule giving O · broadcasting time (D log2). Gaber and Mansour [43] showed that for any packet radio network O there is a schedule of broadcasting giving time (D + log5 n), and that it can be found by a de- terministic polynomial algorithm. Chlamtac and Kutten [18] and Sen and Hun [99] showed the NP-completeness of ﬁnding optimal broadcasting schedules in packet radio networks, in particular it was shown in [99] that the problem remains NP-complete even if the nodes are points in the plane and the reachability is determined by distances. Kirousis, Kranakis, Krizanc and Pelc [65] studied the problem of assigning transmission ranges to nodes located on a line so as to minimize the total power consumption and preserve strong connectedness. This was later extended by Clementi, Fer- reira, Penna, Perennes and Silvestri [28]. Chlamtac and Kutten [19] showed the NP-completeness of minimizing the average time per node during broadcasting when nodes are blocked from hearing messages other than those resulting from a broadcast algorithm. 8 Discussion Most of the material in this chapter concerns single-hop radio networks. This is not surprising as they have been investigated since the beginning of the 1970’s, while the research concerning distributed randomized communication in ad-hoc data radio networks is much newer and goes back to the middle of the 1980’s. While the multiple access channel has been investigated over the years, ﬁrst the inﬁnitely-many users model was dominant but later the research shifted to the ﬁnitely-many users model. The original popularity of the inﬁnitely-many users model seems to have stemmed from the belief that it was a clean model to prove a good behavior of nice protocols in a situation when the number of stations may be arbitrarily large. Later on, after it has been shown that such protocols like Aloha and both the polynomial and exponential backoﬀs are not stable in this model, the ﬁnitely-many users model became more popular. Does the existing body of research provide evidence that results for the inﬁnitely-many users model are less meaningful in general because the model “distorts” the true behavior of protocols? We believe that this is not the case, the following are some of the reasons. First, the stability of superlinear polynomial backoﬀ protocols in the ﬁnitely-many users model simply conﬁrms the stabilizing eﬀect, for this class of protocols, of a scenario when messages can be queued, as opposed to a more challenging situation when messages run protocols on their own. Secondly, the existence of constant-delay protocols for both of these models shows that such ultimate good behavior is possible in both models. The multiple access channel is widely used in existing distributed systems. This popularity has created a common belief that certain speciﬁc protocols used, like the one governing conﬂict resolution in Ethernet, and exponential backoﬀ protocols in general, are the best to provide simple and eﬃcient communication in local area networks. This is in contrast with recent theoretical work, let us quote [58]: “Based on our analysis, it would appear that the most popular and well-studied protocols are precisely the wrong protocols.” This statement is apparently meant to be restricted to backoﬀ protocols. Only recently protocols with a constant expected message delay have been found, which are not backoﬀ but still are acknowledgement-based, their development is a major progress in our understanding how to operate the multiple access channel. To sum this up, issues related to communication in single-hop radio networks seem to be quite well understood, due to the intensive research eﬀort over the past thirty years. Multi-hop radio 33

text: the

text: networks

text: are

text: known

text: then,

text: and

text: are

text: inputs

text: to

text: such

text: sequential

text: algorithms.

text: Chlamtac

text: and

text: We-

text: instein

text: developed

text: a

text: deterministic

text: algorithm

text: which

text: ﬁnds

text: in

text: polynomial

text: time

text: a

text: schedule

text: giving

text: O

text: broadcasting

text: time

text: (D

text: Gaber

text: and

text: Mansour

text: showed

text: that

text: for

text: any

text: packet

text: radio

text: network

text: O

text: there

text: is

text: a

text: schedule

text: of

text: broadcasting

text: giving

text: time

text: (D

text: n),

text: and

text: that

text: it

text: can

text: be

text: found

text: by

text: a

text: de-

text: terministic

text: polynomial

text: algorithm.

text: Chlamtac

text: and

text: Kutten

text: and

text: Sen

text: and

text: Hun

text: showed

text: the

text: NP-completeness

text: of

text: ﬁnding

text: optimal

text: broadcasting

text: schedules

text: in

text: packet

text: radio

text: networks,

text: in

text: particular

text: it

text: was

text: shown

text: in

text: that

text: the

text: problem

text: remains

text: NP-complete

text: even

text: if

text: the

text: nodes

text: are

text: points

text: in

text: the

text: plane

text: and

text: the

text: reachability

text: is

text: determined

text: by

text: distances.

text: Kirousis,

text: Kranakis,

text: Krizanc

text: and

text: Pelc

text: studied

text: the

text: problem

text: of

text: assigning

text: transmission

text: ranges

text: to

text: nodes

text: located

text: on

text: a

text: line

text: so

text: as

text: to

text: minimize

text: the

text: total

text: power

text: consumption

text: and

text: preserve

text: strong

text: connectedness.

text: This

text: was

text: later

text: extended

text: by

text: Clementi,

text: Fer-

text: reira,

text: Penna,

text: Perennes

text: and

text: Silvestri

text: Chlamtac

text: and

text: Kutten

text: showed

text: the

text: NP-completeness

text: of

text: minimizing

text: the

text: average

text: time

text: per

text: node

text: during

text: broadcasting

text: when

text: nodes

text: are

text: blocked

text: from

text: hearing

text: messages

text: other

text: than

text: those

text: resulting

text: from

text: a

text: broadcast

text: algorithm.

text: Discussion

text: Most

text: of

text: the

text: material

text: in

text: this

text: chapter

text: concerns

text: single-hop

text: radio

text: networks.

text: This

text: is

text: not

text: surprising

text: as

text: they

text: have

text: been

text: investigated

text: since

text: the

text: beginning

text: of

text: the

text: while

text: the

text: research

text: concerning

text: distributed

text: randomized

text: communication

text: in

text: ad-hoc

text: data

text: radio

text: networks

text: is

text: much

text: newer

text: and

text: goes

text: back

text: to

text: the

text: middle

text: of

text: the

text: While

text: the

text: multiple

text: access

text: channel

text: has

text: been

text: investigated

text: over

text: the

text: years,

text: ﬁrst

text: the

text: inﬁnitely-many

text: users

text: model

text: was

text: dominant

text: but

text: later

text: the

text: research

text: shifted

text: to

text: the

text: ﬁnitely-many

text: users

text: model.

text: The

text: original

text: popularity

text: of

text: the

text: inﬁnitely-many

text: users

text: model

text: seems

text: to

text: have

text: stemmed

text: from

text: the

text: belief

text: that

text: it

text: was

text: a

text: clean

text: model

text: to

text: prove

text: a

text: good

text: behavior

text: of

text: nice

text: protocols

text: in

text: a

text: situation

text: when

text: the

text: number

text: of

text: stations

text: may

text: be

text: arbitrarily

text: large.

text: Later

text: on,

text: after

text: it

text: has

text: been

text: shown

text: that

text: such

text: protocols

text: like

text: Aloha

text: and

text: both

text: the

text: polynomial

text: and

text: exponential

text: backoﬀs

text: are

text: not

text: stable

text: in

text: this

text: model,

text: the

text: ﬁnitely-many

text: users

text: model

text: became

text: more

text: popular.

text: Does

text: the

text: existing

text: body

text: of

text: research

text: provide

text: evidence

text: that

text: results

text: for

text: the

text: inﬁnitely-many

text: users

text: model

text: are

text: less

text: meaningful

text: in

text: general

text: because

text: the

text: model

text: “distorts”

text: the

text: true

text: behavior

text: of

text: protocols?

text: We

text: believe

text: that

text: this

text: is

text: not

text: the

text: case,

text: the

text: following

text: are

text: some

text: of

text: the

text: reasons.

text: First,

text: the

text: stability

text: of

text: superlinear

text: polynomial

text: backoﬀ

text: protocols

text: in

text: the

text: ﬁnitely-many

text: users

text: model

text: simply

text: conﬁrms

text: the

text: stabilizing

text: eﬀect,

text: for

text: this

text: class

text: of

text: protocols,

text: of

text: a

text: scenario

text: when

text: messages

text: can

text: be

text: queued,

text: as

text: opposed

text: to

text: a

text: more

text: challenging

text: situation

text: when

text: messages

text: run

text: protocols

text: on

text: their

text: own.

text: Secondly,

text: the

text: existence

text: of

text: constant-delay

text: protocols

text: for

text: both

text: of

text: these

text: models

text: shows

text: that

text: such

text: ultimate

text: good

text: behavior

text: is

text: possible

text: in

text: both

text: models.

text: The

text: multiple

text: access

text: channel

text: is

text: widely

text: used

text: in

text: existing

text: distributed

text: systems.

text: This

text: popularity

text: has

text: created

text: a

text: common

text: belief

text: that

text: certain

text: speciﬁc

text: protocols

text: used,

text: like

text: the

text: one

text: governing

text: conﬂict

text: resolution

text: in

text: Ethernet,

text: and

text: exponential

text: backoﬀ

text: protocols

text: in

text: general,

text: are

text: the

text: best

text: to

text: provide

text: simple

text: and

text: eﬃcient

text: communication

text: in

text: local

text: area

text: networks.

text: This

text: is

text: in

text: contrast

text: with

text: recent

text: theoretical

text: work,

text: let

text: us

text: quote

text: “Based

text: on

text: our

text: analysis,

text: it

text: would

text: appear

text: that

text: the

text: most

text: popular

text: and

text: well-studied

text: protocols

text: are

text: precisely

text: the

text: wrong

text: protocols.”

text: This

text: statement

text: is

text: apparently

text: meant

text: to

text: be

text: restricted

text: to

text: backoﬀ

text: protocols.

text: Only

text: recently

text: protocols

text: with

text: a

text: constant

text: expected

text: message

text: delay

text: have

text: been

text: found,

text: which

text: are

text: not

text: backoﬀ

text: but

text: still

text: are

text: acknowledgement-based,

text: their

text: development

text: is

text: a

text: major

text: progress

text: in

text: our

text: understanding

text: how

text: to

text: operate

text: the

text: multiple

text: access

text: channel.

text: To

text: sum

text: this

text: up,

text: issues

text: related

text: to

text: communication

text: in

text: single-hop

text: radio

text: networks

text: seem

text: to

text: be

text: quite

text: well

text: understood,

text: due

text: to

text: the

text: intensive

text: research

text: eﬀort

text: over

text: the

text: past

text: thirty

text: years.

text: Multi-hop

text: radio


text: [107] Wojciech Szpankowski and Vernon Rego. Some theorems on instability with applications to multiaccess protocols. Operations Research, 36(6):958–966, 1988. [108] Andrew S. Tanenbaum and David Wetherall. Computer Networks. Prentice Hall, ﬁfth edition, 2010. [109] John N. Tsitsiklis. Analysis of a multiaccess control scheme. IEEE Transactions on Automatic Control, 32(11):1017–1020, 1987. [110] Boris S. Tsybakov. Survey of USSR contributions to random multiple-access communications. IEEE Transactions on Information Theory, 31(2):143–165, 1985. [111] Boris S. Tsybakov and Nikolay B. Likhanov. Upper bound on the capacity of a random multiple-access system. Problemy Peredachi Informatsii, 23(3):64–78, 1987. [112] Boris S. Tsybakov and Victor A. Mikhailov. Ergodicity of a slotted ALOHA system. Problemy Peredachi Informatsii, 15(4):301–312, 1979. [113] Boris S. Tsybakov and Viktor A. Mikhailov. Free synchronous packet access in a broadcast channel with feedback. Problemy Peredachi Informatsii, 14(4):32–59, 1978. [114] Boris S. Tsybakov and Viktor A. Mikhailov. Random multiple packet access: Part-and-try algorithm. Problemy Peredachi Informatsii, 16(4):65–79, 1980. [115] Sergio Verdu´. Computation of the eﬃciency of the Mosely-Humblet contention resolution algorithm: a simple method. Proceedings of the IEEE, 74(4):613–614, 1986. [116] Nikita D. Vvedenskaya and Mark S. Pinsker. Non-optimality of the part-and-try algorithm. In Abstracts of the International Workshop on Convolutional Codes and Multiuser Commu- nication, pages 141–148, Sochi, USRR, 1983. [117] Dan E. Willard. Log-logarithmic selection resolution protocols in a multiple access channel. SIAM Journal on Computing, 15(2):468–477, 1986. 42

label: reference

text: Wojciech

text: Szpankowski

text: and

text: Vernon

text: Rego.

text: Some

text: theorems

text: on

text: instability

text: with

text: applications

text: to

text: multiaccess

text: protocols.

text: Operations

text: Research,

text: Andrew

text: S.

text: Tanenbaum

text: and

text: David

text: Wetherall.

text: Computer

text: Networks.

text: Prentice

text: Hall,

text: ﬁfth

text: edition,

text: John

text: N.

text: Tsitsiklis.

text: Analysis

text: of

text: a

text: multiaccess

text: control

text: scheme.

text: IEEE

text: Transactions

text: on

text: Automatic

text: Control,

text: Boris

text: S.

text: Tsybakov.

text: Survey

text: of

text: USSR

text: contributions

text: to

text: random

text: multiple-access

text: communications.

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: Boris

text: S.

text: Tsybakov

text: and

text: Nikolay

text: B.

text: Likhanov.

text: Upper

text: bound

text: on

text: the

text: capacity

text: of

text: a

text: random

text: multiple-access

text: system.

text: Problemy

text: Peredachi

text: Informatsii,

text: Boris

text: S.

text: Tsybakov

text: and

text: Victor

text: A.

text: Mikhailov.

text: Ergodicity

text: of

text: a

text: slotted

text: ALOHA

text: system.

text: Problemy

text: Peredachi

text: Informatsii,

text: Boris

text: S.

text: Tsybakov

text: and

text: Viktor

text: A.

text: Mikhailov.

text: Free

text: synchronous

text: packet

text: access

text: in

text: a

text: broadcast

text: channel

text: with

text: feedback.

text: Problemy

text: Peredachi

text: Informatsii,

text: Boris

text: S.

text: Tsybakov

text: and

text: Viktor

text: A.

text: Mikhailov.

text: Random

text: multiple

text: packet

text: access:

text: Part-and-try

text: algorithm.

text: Problemy

text: Peredachi

text: Informatsii,

text: Sergio

text: Verdu´.

text: Computation

text: of

text: the

text: eﬃciency

text: of

text: the

text: Mosely-Humblet

text: contention

text: resolution

text: algorithm:

text: a

text: simple

text: method.

text: Proceedings

text: of

text: the

text: IEEE,

text: Nikita

text: D.

text: Vvedenskaya

text: and

text: Mark

text: S.

text: Pinsker.

text: Non-optimality

text: of

text: the

text: part-and-try

text: algorithm.

text: In

text: Abstracts

text: of

text: the

text: International

text: Workshop

text: on

text: Convolutional

text: Codes

text: and

text: Multiuser

text: Commu-

text: nication,

text: pages

text: Sochi,

text: USRR,

text: Dan

text: E.

text: Willard.

text: Log-logarithmic

text: selection

text: resolution

text: protocols

text: in

text: a

text: multiple

text: access

text: channel.

text: SIAM

text: Journal

text: on

text: Computing,


text: ﬁnite, respectively. Having an inﬁnite collection of stations may seem to be strange at ﬁrst, but the motivation is to treat messages as running protocols themselves, independently from the other messages. We distinguish the following four settings. In a static ﬁnitely-many users model there are a total of n stations, some k stations among them are allocated messages prior to the start of a protocol. Each of the numbers k and n may either be known or not to the stations. In a static inﬁnitely-many users model there are countably inﬁnitely many stations. Each of them performs a Bernoulli trial with some probability p of success prior to the start of a protocol. A success results in a message placed at the station, whereas a failure means that there is no message located there and never will. The probability p is referred to as the probability to hold a message. A dynamic ﬁnitely-many users model is speciﬁed, ﬁrst, by the number n of stations, and sec- ondly, by the mode of arrivals of messages. Usually the arrival process is Bernoulli, that is, in each step at each station a message is generated with some constant probability p, independently of the other stations and steps. Each station has a buﬀer of potentially unbounded capacity, to store backlogged messages. It operates as a queue, that is, on the ﬁrst-come-ﬁrst-served basis. Otherwise, it it operated on the ﬁrst-come-last-served basis, then some protocols in which each message is eventually dispatched successfully with a queue would deteriorate in such a way that the probability that a message is eventually sent is less than one. The current size of the queue of the i-th station is usually denoted as q . i In a dynamic inﬁnitely-many users model the number of stations is again countably inﬁnite. In each step a number of new messages are generated. Each of the messages is allocated to a new station. A station is identiﬁed by the time it obtained a message to transmit. The number of messages generated in a step has a ﬁxed distribution, exactly k new messages are generated in a step with some probability λ . If it is not stated otherwise then the distribution is Poisson with −k parameter λ, that is, λ = e λλk/k! (throughout this article e is the base of the natural logarithm). k Variations on the theme of models are possible. For instance, a static ﬁnitely-many users model may be deﬁned by stipulating that some N messages have arrived, with the arrival times being real numbers in the interval (0, 1) generated by a Poisson process, where simultaneously there are N stations, each station learns its corresponding message at its arrival time (see [91]). For the static ﬁnitely-many users model two tasks are of interest. First is to make some station successfully transmit its packet, which is the static selection problem. Second is to make all the k stations with packets transmit successfully, which is the static all-broadcast problem. For the static inﬁnitely-many users model, the task is to make each message broadcast successfully with probability one, simultaneously achieving the maximum transmission rate. For the dynamic case, the basic question is whether a given protocol is stable, in the sense that it is practically operational, without the channel eventually getting clogged. We associate a Markov chain with each of the dynamic models. In the ﬁnitely-many users case, a state description includes the sequence of numbers of packets waiting at the stations. In the inﬁnitely-many users model, a state includes the total number of backlogged packets. Stability of protocols is usually expressed in terms of properties of the underlying Markov chain. One might expect diﬀerences in performance of similar protocols if they are analyzed in both the inﬁnite and ﬁnite-numbers-of-users models. Observe that with inﬁnitely many stations a newly generated message may be immediately broadcast on the channel, what contributes to burstiness 5

text: ﬁnite,

text: respectively.

text: Having

text: an

text: inﬁnite

text: collection

text: of

text: stations

text: may

text: seem

text: to

text: be

text: strange

text: at

text: ﬁrst,

text: but

text: the

text: motivation

text: is

text: to

text: treat

text: messages

text: as

text: running

text: protocols

text: themselves,

text: independently

text: from

text: the

text: other

text: messages.

text: We

text: distinguish

text: the

text: following

text: four

text: settings.

text: In

text: a

text: static

text: ﬁnitely-many

text: users

text: model

text: there

text: are

text: a

text: total

text: of

text: n

text: stations,

text: some

text: k

text: stations

text: among

text: them

text: are

text: allocated

text: messages

text: prior

text: to

text: the

text: start

text: of

text: a

text: protocol.

text: Each

text: of

text: the

text: numbers

text: k

text: and

text: n

text: may

text: either

text: be

text: known

text: or

text: not

text: to

text: the

text: stations.

text: In

text: a

text: static

text: inﬁnitely-many

text: users

text: model

text: there

text: are

text: countably

text: inﬁnitely

text: many

text: stations.

text: Each

text: of

text: them

text: performs

text: a

text: Bernoulli

text: trial

text: with

text: some

text: probability

text: p

text: of

text: success

text: prior

text: to

text: the

text: start

text: of

text: a

text: protocol.

text: A

text: success

text: results

text: in

text: a

text: message

text: placed

text: at

text: the

text: station,

text: whereas

text: a

text: failure

text: means

text: that

text: there

text: is

text: no

text: message

text: located

text: there

text: and

text: never

text: will.

text: The

text: probability

text: p

text: is

text: referred

text: to

text: as

text: the

text: probability

text: to

text: hold

text: a

text: message.

text: A

text: dynamic

text: ﬁnitely-many

text: users

text: model

text: is

text: speciﬁed,

text: ﬁrst,

text: by

text: the

text: number

text: n

text: of

text: stations,

text: and

text: sec-

text: ondly,

text: by

text: the

text: mode

text: of

text: arrivals

text: of

text: messages.

text: Usually

text: the

text: arrival

text: process

text: is

text: Bernoulli,

text: that

text: is,

text: in

text: each

text: step

text: at

text: each

text: station

text: a

text: message

text: is

text: generated

text: with

text: some

text: constant

text: probability

text: p,

text: independently

text: of

text: the

text: other

text: stations

text: and

text: steps.

text: Each

text: station

text: has

text: a

text: buﬀer

text: of

text: potentially

text: unbounded

text: capacity,

text: to

text: store

text: backlogged

text: messages.

text: It

text: operates

text: as

text: a

text: queue,

text: that

text: is,

text: on

text: the

text: ﬁrst-come-ﬁrst-served

text: basis.

text: Otherwise,

text: it

text: it

text: operated

text: on

text: the

text: ﬁrst-come-last-served

text: basis,

text: then

text: some

text: protocols

text: in

text: which

text: each

text: message

text: is

text: eventually

text: dispatched

text: successfully

text: with

text: a

text: queue

text: would

text: deteriorate

text: in

text: such

text: a

text: way

text: that

text: the

text: probability

text: that

text: a

text: message

text: is

text: eventually

text: sent

text: is

text: less

text: than

text: one.

text: The

text: current

text: size

text: of

text: the

text: queue

text: of

text: the

text: i-th

text: station

text: is

text: usually

text: denoted

text: as

text: q

text: i

text: In

text: a

text: dynamic

text: inﬁnitely-many

text: users

text: model

text: the

text: number

text: of

text: stations

text: is

text: again

text: countably

text: inﬁnite.

text: In

text: each

text: step

text: a

text: number

text: of

text: new

text: messages

text: are

text: generated.

text: Each

text: of

text: the

text: messages

text: is

text: allocated

text: to

text: a

text: new

text: station.

text: A

text: station

text: is

text: identiﬁed

text: by

text: the

text: time

text: it

text: obtained

text: a

text: message

text: to

text: transmit.

text: The

text: number

text: of

text: messages

text: generated

text: in

text: a

text: step

text: has

text: a

text: ﬁxed

text: distribution,

text: exactly

text: k

text: new

text: messages

text: are

text: generated

text: in

text: a

text: step

text: with

text: some

text: probability

text: λ

text: If

text: it

text: is

text: not

text: stated

text: otherwise

text: then

text: the

text: distribution

text: is

text: Poisson

text: with

text: −k

text: parameter

text: λ,

text: that

text: is,

text: λ

text: e

text: λλk/k!

text: (throughout

text: this

text: article

text: e

text: is

text: the

text: base

text: of

text: the

text: natural

text: logarithm).

text: k

text: Variations

text: on

text: the

text: theme

text: of

text: models

text: are

text: possible.

text: For

text: instance,

text: a

text: static

text: ﬁnitely-many

text: users

text: model

text: may

text: be

text: deﬁned

text: by

text: stipulating

text: that

text: some

text: N

text: messages

text: have

text: arrived,

text: with

text: the

text: arrival

text: times

text: being

text: real

text: numbers

text: in

text: the

text: interval

text: generated

text: by

text: a

text: Poisson

text: process,

text: where

text: simultaneously

text: there

text: are

text: N

text: stations,

text: each

text: station

text: learns

text: its

text: corresponding

text: message

text: at

text: its

text: arrival

text: time

text: (see

text: For

text: the

text: static

text: ﬁnitely-many

text: users

text: model

text: two

text: tasks

text: are

text: of

text: interest.

text: First

text: is

text: to

text: make

text: some

text: station

text: successfully

text: transmit

text: its

text: packet,

text: which

text: is

text: the

text: static

text: selection

text: problem.

text: Second

text: is

text: to

text: make

text: all

text: the

text: k

text: stations

text: with

text: packets

text: transmit

text: successfully,

text: which

text: is

text: the

text: static

text: all-broadcast

text: problem.

text: For

text: the

text: static

text: inﬁnitely-many

text: users

text: model,

text: the

text: task

text: is

text: to

text: make

text: each

text: message

text: broadcast

text: successfully

text: with

text: probability

text: one,

text: simultaneously

text: achieving

text: the

text: maximum

text: transmission

text: rate.

text: For

text: the

text: dynamic

text: case,

text: the

text: basic

text: question

text: is

text: whether

text: a

text: given

text: protocol

text: is

text: stable,

text: in

text: the

text: sense

text: that

text: it

text: is

text: practically

text: operational,

text: without

text: the

text: channel

text: eventually

text: getting

text: clogged.

text: We

text: associate

text: a

text: Markov

text: chain

text: with

text: each

text: of

text: the

text: dynamic

text: models.

text: In

text: the

text: ﬁnitely-many

text: users

text: case,

text: a

text: state

text: description

text: includes

text: the

text: sequence

text: of

text: numbers

text: of

text: packets

text: waiting

text: at

text: the

text: stations.

text: In

text: the

text: inﬁnitely-many

text: users

text: model,

text: a

text: state

text: includes

text: the

text: total

text: number

text: of

text: backlogged

text: packets.

text: Stability

text: of

text: protocols

text: is

text: usually

text: expressed

text: in

text: terms

text: of

text: properties

text: of

text: the

text: underlying

text: Markov

text: chain.

text: One

text: might

text: expect

text: diﬀerences

text: in

text: performance

text: of

text: similar

text: protocols

text: if

text: they

text: are

text: analyzed

text: in

text: both

text: the

text: inﬁnite

text: and

text: ﬁnite-numbers-of-users

text: models.

text: Observe

text: that

text: with

text: inﬁnitely

text: many

text: stations

text: a

text: newly

text: generated

text: message

text: may

text: be

text: immediately

text: broadcast

text: on

text: the

text: channel,

text: what

text: contributes

text: to

text: burstiness


text: 8 Xing Di, Vishal M. Patel Fig. 9 Comparison of results from diﬀerent conﬁgurations of the proposed network. For all subﬁgures (a) (b) (c) and (d): ﬁrst column: output using the proposed method, second column: output with the speciﬁc conﬁguration, and third column: reference images. (a) Results corresponding to the case where attributes are not used in Stage 3. (b) S2S reconstructions without the use of encoded texture attributes. (c) Results when the second stage of S2S is omitted from the pipeline. Results show reconstructions with wrong attributes. (d) Results when the second stage of S2S is omitted from the pipeline. Poor quality reconstructions are obtained when S2S is skipped from the proposed method. Table 1 List of ﬁne-grained texture and color attributes. much better than the ones where sketches are enhanced directly without conditioning on the attributes. Arched Eyebrows, Bags Under Eyes, Bald, Bangs, Big Lips, Big Nose, Texture Bushy Eyebrows, Chubby, Male, Narrow Eyes, No Beard, Results corresponding to the third experiment are Smiling, Young shown in Figure 9(a), where the ﬁrst, second and third Black Hair, Blond Hair, Brown Hair, Color columns show the reconstruction results from our method, Gray Hair, Pale Skin, Rosy Cheeks reconstructions without using attributes in S2F, and reference images, respectively. As can be seen from this ﬁgure, the absence of attributes in the ﬁnal stage results 1. Omit attributes while enhancing the sketch images in reconstructions with wrong face features such as gen- generated from the A2S stage. This will show the der and hair. When attributes are used along with the signiﬁcance of using attributes while enhancing the sketch from S2S, the produced results have attributes sketch images in the S2S stage. that are very close to the ones corresponding to the 2. Remove the second stage of sketch image enhance- original images. This can be clearly seen by comparing ment from the entire pipeline. In other words, recon- the ﬁrst and last columns in Figure 9(a). struct the face image directly from the blurry sketch generated from A2S without enhancement. This will clearly show the signiﬁcance of the S2S stage. In the ﬁnal experiment, we omit the second stage of 3. Remove the attribute concatenation from the ﬁnal S2S from our pipeline and attempt to reconstruct the S2F stage. This will show the signiﬁcance of using image from attributes in a two-stage procedure. In other attributes in the ﬁnal stage of sketch-to-image gen- words, sketch images generated from the A2S stage are eration. directly fed into the S2F stage. Results are shown in Figure 9(c) and (d). In both ﬁgures, ﬁrst, middle and Results corresponding to the above three conﬁgurations last columns show reconstructions from our method, are shown in Figure 9. Results corresponding to the ﬁrst without the second stage and reference images, respec- experiment are shown in Figure 9(b), where the ﬁrst, tively. As can be seen from these ﬁgures, omission of the second and third columns indicate, the outputs from the S2S stage from our pipeline produces images that are of S2S stage of our method, reconstructions without the poor quality (see results in Figure 9(d)). The enhance- use of attributes in S2S, the reference sketch, respec- ment of sketches in Stage 2 not only produces sharper tively. From this ﬁgure we clearly see that attribute- results but also with correct attributes (see results in conditioned generator G2 produces sketches that are Figure 9(c)). ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Xing

label: author

text: Di,

text: Vishal

text: M.

text: Patel

text: Fig.

text: Comparison

label: caption

text: of

text: results

text: from

text: diﬀerent

text: conﬁgurations

text: of

text: the

text: proposed

text: network.

text: For

text: all

text: subﬁgures

text: (a)

text: (b)

text: (c)

text: and

text: (d):

text: ﬁrst

text: column:

text: output

text: using

text: the

text: proposed

text: method,

text: second

text: column:

text: output

text: with

text: the

text: speciﬁc

text: conﬁguration,

text: and

text: third

text: column:

text: reference

text: images.

text: (a)

text: Results

text: corresponding

text: to

text: the

text: case

text: where

text: attributes

text: are

text: not

text: used

text: in

text: Stage

text: (b)

text: reconstructions

text: without

text: the

text: use

text: of

text: encoded

text: texture

text: attributes.

text: (c)

text: Results

text: when

text: the

text: second

text: stage

text: of

text: is

text: omitted

text: from

text: the

text: pipeline.

text: Results

text: show

text: reconstructions

text: with

text: wrong

text: attributes.

text: (d)

text: Results

text: when

text: the

text: second

text: stage

text: of

text: is

text: omitted

text: from

text: the

text: pipeline.

text: Poor

text: quality

text: reconstructions

text: are

text: obtained

text: when

text: is

text: skipped

text: from

text: the

text: proposed

text: method.

text: Table

text: List

text: of

text: ﬁne-grained

text: texture

text: and

text: color

text: attributes.

text: much

text: better

text: than

text: the

text: ones

text: where

text: sketches

text: are

text: enhanced

text: directly

text: without

text: conditioning

text: on

text: the

text: attributes.

text: Arched

text: Eyebrows,

text: Bags

text: Under

text: Eyes,

text: Bald,

text: Bangs,

text: Big

text: Lips,

text: Big

text: Nose,

text: Texture

text: Bushy

text: Eyebrows,

text: Chubby,

text: Male,

text: Narrow

text: Eyes,

text: No

text: Beard,

text: Results

text: corresponding

text: to

text: the

text: third

text: experiment

text: are

text: Smiling,

text: Young

text: shown

text: in

text: Figure

text: where

text: the

text: ﬁrst,

text: second

text: and

text: third

text: Black

text: Hair,

text: Blond

text: Hair,

text: Brown

text: Hair,

text: Color

text: columns

text: show

text: the

text: reconstruction

text: results

text: from

text: our

text: method,

text: Gray

text: Hair,

text: Pale

text: Skin,

text: Rosy

text: Cheeks

text: reconstructions

text: without

text: using

text: attributes

text: in

text: and

text: reference

text: images,

text: respectively.

text: As

text: can

text: be

text: seen

text: from

text: this

text: ﬁgure,

text: the

text: absence

text: of

text: attributes

text: in

text: the

text: ﬁnal

text: stage

text: results

text: Omit

text: attributes

text: while

text: enhancing

text: the

text: sketch

text: images

text: in

text: reconstructions

text: with

text: wrong

text: face

text: features

text: such

text: as

text: gen-

text: generated

text: from

text: the

text: stage.

text: This

text: will

text: show

text: the

text: der

text: and

text: hair.

text: When

text: attributes

text: are

text: used

text: along

text: with

text: the

text: signiﬁcance

text: of

text: using

text: attributes

text: while

text: enhancing

text: the

text: sketch

text: from

text: the

text: produced

text: results

text: have

text: attributes

text: sketch

text: images

text: in

text: the

text: stage.

text: that

text: are

text: very

text: close

text: to

text: the

text: ones

text: corresponding

text: to

text: the

text: Remove

text: the

text: second

text: stage

text: of

text: sketch

text: image

text: enhance-

text: original

text: images.

text: This

text: can

text: be

text: clearly

text: seen

text: by

text: comparing

text: ment

text: from

text: the

text: entire

text: pipeline.

text: In

text: other

text: words,

text: recon-

text: the

text: ﬁrst

text: and

text: last

text: columns

text: in

text: Figure

text: struct

text: the

text: face

text: image

text: directly

text: from

text: the

text: blurry

text: sketch

text: generated

text: from

text: without

text: enhancement.

text: This

text: will

text: clearly

text: show

text: the

text: signiﬁcance

text: of

text: the

text: stage.

text: In

text: the

text: ﬁnal

text: experiment,

text: we

text: omit

text: the

text: second

text: stage

text: of

text: Remove

text: the

text: attribute

text: concatenation

text: from

text: the

text: ﬁnal

text: from

text: our

text: pipeline

text: and

text: attempt

text: to

text: reconstruct

text: the

text: stage.

text: This

text: will

text: show

text: the

text: signiﬁcance

text: of

text: using

text: image

text: from

text: attributes

text: in

text: a

text: two-stage

text: procedure.

text: In

text: other

text: attributes

text: in

text: the

text: ﬁnal

text: stage

text: of

text: sketch-to-image

text: gen-

text: words,

text: sketch

text: images

text: generated

text: from

text: the

text: stage

text: are

text: eration.

text: directly

text: fed

text: into

text: the

text: stage.

text: Results

text: are

text: shown

text: in

text: Figure

text: and

text: (d).

text: In

text: both

text: ﬁgures,

text: ﬁrst,

text: middle

text: and

text: Results

text: corresponding

text: to

text: the

text: above

text: three

text: conﬁgurations

text: last

text: columns

text: show

text: reconstructions

text: from

text: our

text: method,

text: are

text: shown

text: in

text: Figure

text: Results

text: corresponding

text: to

text: the

text: ﬁrst

text: without

text: the

text: second

text: stage

text: and

text: reference

text: images,

text: respec-

text: experiment

text: are

text: shown

text: in

text: Figure

text: where

text: the

text: ﬁrst,

text: tively.

text: As

text: can

text: be

text: seen

text: from

text: these

text: ﬁgures,

text: omission

text: of

text: the

text: second

text: and

text: third

text: columns

text: indicate,

text: the

text: outputs

text: from

text: the

text: stage

text: from

text: our

text: pipeline

text: produces

text: images

text: that

text: are

text: of

text: stage

text: of

text: our

text: method,

text: reconstructions

text: without

text: the

text: poor

text: quality

text: (see

text: results

text: in

text: Figure

text: The

text: enhance-

text: use

text: of

text: attributes

text: in

text: the

text: reference

text: sketch,

text: respec-

text: ment

text: of

text: sketches

text: in

text: Stage

text: not

text: only

text: produces

text: sharper

text: tively.

text: From

text: this

text: ﬁgure

text: we

text: clearly

text: see

text: that

text: attribute-

text: results

text: but

text: also

text: with

text: correct

text: attributes

text: (see

text: results

text: in

text: conditioned

text: generator

text: produces

text: sketches

text: that

text: are

text: Figure

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: HDG-POD Reduced Order Model of the Heat Equation ∗ † † Jiguang Shen John R. Singler Yangwen Zhang Abstract We propose a new hybridizable discontinuous Galerkin (HDG) model order reduction tech- nique based on proper orthogonal decomposition (POD). We consider the heat equation as a test problem and prove error bounds that converge to zero as the number of POD modes increases. We present 2D and 3D numerical results to illustrate the convergence analysis. 1 Introduction Discontinuous Galerkin (DG) methods for solving partial diﬀerential equations, developed in the late 1990s, have become popular among computational scientists [3, 4, 8, 11, 17]. However, the number of degrees of freedom for DG methods is much larger compared to standard continuous Galerkin (CG) methods; this is typically considered to be the main drawback of DG methods. Hybridizable discontinuous Galerkin (HDG) methods were originally proposed by Cockburn, Gopalakrishnan, and Lazarov in [16] to improve traditional DG methods. HDG methods keep the positive features of DG methods, while simultaneously lowering the number of degrees of freedom. In addition to approximating a scalar variable and its ﬂux, HDG methods also approximate the trace of the scalar variable on the boundary of the mesh. The scalar and ﬂux variables are eliminated element-by-element, which leaves a global system in terms of the approximate scalar trace only. This greatly reduces the number of degrees of freedom compared to other DG methods. Because of the many advantages of HDG methods, they are being actively investigated in many directions; see, e.g., [10,15,18,21,22,27,39–47,50,54]. Although the degrees of freedom for HDG methods is much smaller compared to other DG meth- ods, the resulting discrete systems can have large dimensions for complex applications. Therefore, eﬃcient and accurate model order reduction techniques are desirable. Proper orthogonal decomposition (POD) is a popular model reduction technique that has been successfully used in a variety of ﬁelds including ﬂuid dynamics [25], inverse problems [7], PDE- constrained optimization [23,52], and feedback control [5,34–36,49]. Many researchers have devel- oped POD model reduction schemes for many problems and have proved related error bounds, see, e.g., [1,2,13,14,20,24,26,28,30–33,37,38,53,55,56]. A POD reduced order model of a time dependent partial diﬀerential equation (PDE) is typically constructed in the following way. First, solution data is collected and a POD procedure is used to identify a small or moderate number of global basis functions, called POD modes, that optimally ∗ School of Mathematics, University of Minnesota, MN (shenx179@umn.edu) † Department of Mathematics and Statistics, Missouri University of Science and Technology, Rolla, MO (singlerj@mst.edu, ywzfg4@mst.edu). J. Singler and Y. Zhang were supported in part by National Science Foun- dation grant DMS-1217122. J. Singler and Y. Zhang thank the IMA for funding research visits, during which some of this work was completed. 1 ##LTLine##

text: HDG-POD

label: title

text: Reduced

text: Order

text: Model

text: of

text: the

text: Heat

text: Equation

text: Jiguang

text: Shen

text: John

text: R.

text: Singler

text: Yangwen

text: Zhang

text: Abstract

text: We

label: abstract

text: propose

text: a

text: new

text: hybridizable

text: discontinuous

text: Galerkin

text: (HDG)

text: model

text: order

text: reduction

text: tech-

text: nique

text: based

text: on

text: proper

text: orthogonal

text: decomposition

text: (POD).

text: We

text: consider

text: the

text: heat

text: equation

text: as

text: a

text: test

text: problem

text: and

text: prove

text: error

text: bounds

text: that

text: converge

text: to

text: zero

text: as

text: the

text: number

text: of

text: POD

text: modes

text: increases.

text: We

text: present

text: and

text: numerical

text: results

text: to

text: illustrate

text: the

text: convergence

text: analysis.

text: Introduction

text: Discontinuous

text: Galerkin

text: (DG)

text: methods

text: for

text: solving

text: partial

text: diﬀerential

text: equations,

text: developed

text: in

text: the

text: late

text: have

text: become

text: popular

text: among

text: computational

text: scientists

text: However,

text: the

text: number

text: of

text: degrees

text: of

text: freedom

text: for

text: DG

text: methods

text: is

text: much

text: larger

text: compared

text: to

text: standard

text: continuous

text: Galerkin

text: (CG)

text: methods;

text: this

text: is

text: typically

text: considered

text: to

text: be

text: the

text: main

text: drawback

text: of

text: DG

text: methods.

text: Hybridizable

text: discontinuous

text: Galerkin

text: (HDG)

text: methods

text: were

text: originally

text: proposed

text: by

text: Cockburn,

text: Gopalakrishnan,

text: and

text: Lazarov

text: in

text: to

text: improve

text: traditional

text: DG

text: methods.

text: HDG

text: methods

text: keep

text: the

text: positive

text: features

text: of

text: DG

text: methods,

text: while

text: simultaneously

text: lowering

text: the

text: number

text: of

text: degrees

text: of

text: freedom.

text: In

text: addition

text: to

text: approximating

text: a

text: scalar

text: variable

text: and

text: its

text: ﬂux,

text: HDG

text: methods

text: also

text: approximate

text: the

text: trace

text: of

text: the

text: scalar

text: variable

text: on

text: the

text: boundary

text: of

text: the

text: mesh.

text: The

text: scalar

text: and

text: ﬂux

text: variables

text: are

text: eliminated

text: element-by-element,

text: which

text: leaves

text: a

text: global

text: system

text: in

text: terms

text: of

text: the

text: approximate

text: scalar

text: trace

text: only.

text: This

text: greatly

text: reduces

text: the

text: number

text: of

text: degrees

text: of

text: freedom

text: compared

text: to

text: other

text: DG

text: methods.

text: Because

text: of

text: the

text: many

text: advantages

text: of

text: HDG

text: methods,

text: they

text: are

text: being

text: actively

text: investigated

text: in

text: many

text: directions;

text: see,

text: e.g.,

text: Although

text: the

text: degrees

text: of

text: freedom

text: for

text: HDG

text: methods

text: is

text: much

text: smaller

text: compared

text: to

text: other

text: DG

text: meth-

text: ods,

text: the

text: resulting

text: discrete

text: systems

text: can

text: have

text: large

text: dimensions

text: for

text: complex

text: applications.

text: Therefore,

text: eﬃcient

text: and

text: accurate

text: model

text: order

text: reduction

text: techniques

text: are

text: desirable.

text: Proper

text: orthogonal

text: decomposition

text: (POD)

text: is

text: a

text: popular

text: model

text: reduction

text: technique

text: that

text: has

text: been

text: successfully

text: used

text: in

text: a

text: variety

text: of

text: ﬁelds

text: including

text: ﬂuid

text: dynamics

text: inverse

text: problems

text: PDE-

text: constrained

text: optimization

text: and

text: feedback

text: control

text: Many

text: researchers

text: have

text: devel-

text: oped

text: POD

text: model

text: reduction

text: schemes

text: for

text: many

text: problems

text: and

text: have

text: proved

text: related

text: error

text: bounds,

text: see,

text: e.g.,

text: A

text: POD

text: reduced

text: order

text: model

text: of

text: a

text: time

text: dependent

text: partial

text: diﬀerential

text: equation

text: (PDE)

text: is

text: typically

text: constructed

text: in

text: the

text: following

text: way.

text: First,

text: solution

text: data

text: is

text: collected

text: and

text: a

text: POD

text: procedure

text: is

text: used

text: to

text: identify

text: a

text: small

text: or

text: moderate

text: number

text: of

text: global

text: basis

text: functions,

text: called

text: POD

text: modes,

text: that

text: optimally

text: School

text: of

text: Mathematics,

text: University

text: of

text: Minnesota,

text: MN

text: Department

text: of

text: Mathematics

text: and

text: Statistics,

text: Missouri

text: University

text: of

text: Science

text: and

text: Technology,

text: Rolla,

text: MO

text: (singlerj@mst.edu,

text: J.

text: Singler

text: and

text: Y.

text: Zhang

text: were

text: supported

text: in

text: part

text: by

text: National

text: Science

text: Foun-

text: dation

text: grant

text: J.

text: Singler

text: and

text: Y.

text: Zhang

text: thank

text: the

text: IMA

text: for

text: funding

text: research

text: visits,

text: during

text: which

text: some

text: of

text: this

text: work

text: was

text: completed.

text: ##LTLine##


text: ∈ ∈ where f L2(0, T ; L2(Ω)) is the source function, u L2(Ω) is the initial condition, and ∈ ∞ 0 a L (Ω) is the coeﬃcient function. We assume there exist positive constants c and c such that ≤ − ≤ 0 1 0 < c a 1 c . 0 1 2.1 HDG Next, we brieﬂy describe an HDG method for the heat equation, which was analyzed in [12]. Let T T { ∈ T } be a collection of disjoint elements that partition Ω. We let ∂ denote the set ∂K : K . h T ∩ h − h For an element K of the collection , e = ∂K Γ is a boundary face if the d 1 Lebesgue measure h − T ∩ − of e is nonzero. For two elements K+ and K of the collection , e = ∂K+ ∂K is the interior − − h face between K+ and K if the d 1 Lebesgue measure of e is nonzero. Let ε∂ and εo denote the h h set of boundary faces and interior(cid:88)faces, respectively, and we le(cid:88)t ε denote the union of εo and ε∂. h h h We ﬁnally introduce (cid:104) (cid:105) (cid:104) (cid:105) (w, v)T = (w, v) , ζ, ρ T = ζ, ρ . h ∈T K ∂ h ∈T ∂K K K h h 2.1.1 The HDG Formulation: Discretization in Space − ∇ − The HDG method introduces the ﬂux q = a u as an unknown. For c = a 1, the heat equation (1) can be rewritten as − ∇ · (cid:104) · (cid:105) (cq, v)T (u, v)T + u, v n T = 0, (2a) h − ∇ h (cid:104) · (cid:105)∂ h (u , w)T (q, w)T + q n, w T = (f, w)T , (2b) t h h (cid:104) · (cid:105) ∂ h h q n, µ T \ = 0, (2c) ∂ ε∂ (cid:104) h(cid:105) h u, µ = 0, (2d) ε∂ · h (u( , 0), w)T = (u , w)T , (2e) 0 h h ∈ × × for all (v, w, µ) H(div, Ω) L2(Ω) L2(ε ). P h Let k(D) denote the set of polynomials of degree at most k on a domain D. We introduce the discontinuous ﬁnite element spaces { ∈ | ∈ P ∀ ∈ T } V := v [L2(Ω)]d : v [ k(K)]d, K , h K h { ∈ | ∈ P ∀ ∈ T } W := w L2(Ω) : w k(K), K , (3) h K h { ∈ | ∈ P ∀ ∈ | } M := µ L2(ε ) : µ k(e), e ε , µ = 0 . h h e h ε∂ h ∈ Note that Mh consists of functions that are contin(cid:98)uous inside the faces (or edges) e εh and discontinuous at their borders. ∈ × × The HDG method seeks an approximation (q , u , u ) V W M such that h h h h h h (cid:98) − ∇ · (cid:104)(cid:98) · (cid:105) (cq , v)T (u , v)T + u , v n T = 0, (4a) h h − h ∇ h (cid:98)(cid:104) h· (cid:105)∂ h (∂ u , w)T (q , w)T + q n, w T = (f, w)T , (4b) t h h h h (cid:104) ·h (cid:105) ∂ h h q n, µ T \ = 0, (4c) h ∂ ε∂ · h h (u ( , 0), w)T = (u , w)T , (4d) h h 0 h 3

text: where

text: f

text: T

text: is

text: the

text: source

text: function,

text: u

text: is

text: the

text: initial

text: condition,

text: and

text: a

text: L

text: (Ω)

text: is

text: the

text: coeﬃcient

text: function.

text: We

text: assume

text: there

text: exist

text: positive

text: constants

text: c

text: and

text: c

text: such

text: that

text: c

text: a

text: c

text: HDG

text: Next,

text: we

text: brieﬂy

text: describe

text: an

text: HDG

text: method

text: for

text: the

text: heat

text: equation,

text: which

text: was

text: analyzed

text: in

text: Let

text: T

text: T

text: T

text: be

text: a

text: collection

text: of

text: disjoint

text: elements

text: that

text: partition

text: Ω.

text: We

text: let

text: denote

text: the

text: set

text: ∂K

text: K

text: h

text: T

text: h

text: h

text: For

text: an

text: element

text: K

text: of

text: the

text: collection

text: e

text: ∂K

text: Γ

text: is

text: a

text: boundary

text: face

text: if

text: the

text: d

text: Lebesgue

text: measure

text: h

text: T

text: of

text: e

text: is

text: nonzero.

text: For

text: two

text: elements

text: K+

text: and

text: K

text: of

text: the

text: collection

text: e

text: ∂K+

text: ∂K

text: is

text: the

text: interior

text: h

text: face

text: between

text: K+

text: and

text: K

text: if

text: the

text: d

text: Lebesgue

text: measure

text: of

text: e

text: is

text: nonzero.

text: Let

text: ε∂

text: and

text: εo

text: denote

text: the

text: h

text: h

text: set

text: of

text: boundary

text: faces

text: and

text: respectively,

text: and

text: we

text: ε

text: denote

text: the

text: union

text: of

text: εo

text: and

text: ε∂.

text: h

text: h

text: h

text: We

text: ﬁnally

text: introduce

text: (w,

text: v)T

text: (w,

text: v)

text: ζ,

text: ρ

text: T

text: ζ,

text: ρ

text: h

text: ∈T

text: K

text: h

text: ∈T

text: ∂K

text: K

text: K

text: h

text: h

text: The

text: HDG

text: Formulation:

text: Discretization

text: in

text: Space

text: The

text: HDG

text: method

text: introduces

text: the

text: ﬂux

text: q

text: a

text: u

text: as

text: an

text: unknown.

text: For

text: c

text: a

text: the

text: heat

text: equation

text: can

text: be

text: rewritten

text: as

text: (cq,

text: v)T

text: (u,

text: v)T

text: u,

text: v

text: n

text: T

text: h

text: h

text: h

text: (u

text: w)T

text: (q,

text: w)T

text: q

text: n,

text: w

text: T

text: (f,

text: w)T

text: t

text: h

text: h

text: h

text: h

text: q

text: n,

text: µ

text: T

text: ε∂

text: h

text: u,

text: µ

text: ε∂

text: h

text: (u(

text: w)T

text: (u

text: w)T

text: h

text: h

text: for

text: all

text: (v,

text: w,

text: µ)

text: H(div,

text: Ω)

text: P

text: h

text: Let

text: k(D)

text: denote

text: the

text: set

text: of

text: polynomials

text: of

text: degree

text: at

text: most

text: k

text: on

text: a

text: domain

text: D.

text: We

text: introduce

text: the

text: discontinuous

text: ﬁnite

text: element

text: spaces

text: P

text: T

text: V

text: v

text: v

text: k(K)]d,

text: K

text: h

text: K

text: h

text: P

text: T

text: W

text: w

text: w

text: k(K),

text: K

text: h

text: K

text: h

text: P

text: M

text: µ

text: µ

text: k(e),

text: e

text: ε

text: µ

text: h

text: h

text: e

text: h

text: ε∂

text: h

text: Note

text: that

text: Mh

text: consists

text: of

text: functions

text: that

text: are

text: inside

text: the

text: faces

text: (or

text: edges)

text: e

text: εh

text: and

text: discontinuous

text: at

text: their

text: borders.

text: The

text: HDG

text: method

text: seeks

text: an

text: approximation

text: (q

text: u

text: u

text: V

text: W

text: M

text: such

text: that

text: h

text: h

text: h

text: h

text: h

text: h

text: (cq

text: v)T

text: (u

text: v)T

text: u

text: v

text: n

text: T

text: h

text: h

text: h

text: h

text: h·

text: h

text: u

text: w)T

text: (q

text: w)T

text: q

text: n,

text: w

text: T

text: (f,

text: w)T

text: t

text: h

text: h

text: h

text: h

text: ·h

text: h

text: h

text: q

text: n,

text: µ

text: T

text: h

text: ε∂

text: h

text: h

text: (u

text: w)T

text: (u

text: w)T

text: h

text: h

text: h


text: [8] F. Bassi and S. Rebay. A high-order accurate discontinuous ﬁnite element method for the numerical solution of the compressible Navier-Stokes equations. J. Comput. Phys., 131(2):267– 279, 1997. [9] Matthew Brand. Fast low-rank modiﬁcations of the thin singular value decomposition. Linear Algebra Appl., 415(1):20–30, 2006. [10] Tan Bui-Thanh. Construction and analysis of HDG methods for linearized shallow water equations. SIAM J. Sci. Comput., 38(6):A3696–A3719, 2016. [11] Paul Castillo, Bernardo Cockburn, Ilaria Perugia, and Dominik Sch¨otzau. An a priori error analysis of the local discontinuous Galerkin method for elliptic problems. SIAM J. Numer. Anal., 38(5):1676–1706, 2000. [12] Brandon Chabaud and Bernardo Cockburn. Uniform-in-time superconvergence of HDG meth- ods for the heat equation. Math. Comp., 81(277):107–129, 2012. [13] D. Chapelle, A. Gariah, P. Moireau, and J. Sainte-Marie. A Galerkin strategy with proper orthogonal decomposition for parameter-dependent problems—analysis, assessments and ap- plications to parameter estimation. ESAIM Math. Model. Numer. Anal., 47(6):1821–1843, 2013. [14] Dominique Chapelle, Asven Gariah, and Jacques Sainte-Marie. Galerkin approximation with proper orthogonal decomposition: new error estimates and illustrative examples. ESAIM Math. Model. Numer. Anal., 46(4):731–757, 2012. [15] Bernardo Cockburn, Bo Dong, Johnny Guzm´an, Marco Restelli, and Riccardo Sacco. A hy- bridizable discontinuous Galerkin method for steady-state convection-diﬀusion-reaction prob- lems. SIAM J. Sci. Comput., 31(5):3827–3846, 2009. [16] Bernardo Cockburn, Jayadeep Gopalakrishnan, and Raytcho Lazarov. Uniﬁed hybridization of discontinuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems. SIAM J. Numer. Anal., 47(2):1319–1365, 2009. [17] Bernardo Cockburn and Chi-Wang Shu. The local discontinuous Galerkin method for time- dependent convection-diﬀusion systems. SIAM J. Numer. Anal., 35(6):2440–2463, 1998. [18] Jintao Cui and Wujun Zhang. An analysis of HDG methods for the Helmholtz equation. IMA J. Numer. Anal., 34(1):279–295, 2014. [19] Hiba Fareed, Jiguang Shen, John R. Singler, and Yangwen Zhang. Incremental proper orthog- onal decomposition for PDE simulation data. Computers & Mathematics with Applications. to appear. [20] Pedro Gal´an del Sastre and Rodolfo Bermejo. Error estimates of proper orthogonal decom- position eigenvectors and Galerkin projection for a general dynamical system arising in ﬂuid models. Numer. Math., 110(1):49–81, 2008. [21] Gabriel N. Gatica and Fil´ander A. Sequeira. A priori and a posteriori error analyses of an aug- mented HDG method for a class of quasi-Newtonian Stokes ﬂows. J. Sci. Comput., 69(3):1192– 1250, 2016. 22

text: F.

text: Bassi

text: and

text: S.

text: Rebay.

text: A

text: high-order

text: accurate

text: discontinuous

text: ﬁnite

text: element

text: method

text: for

text: the

text: numerical

text: solution

text: of

text: the

text: compressible

text: Navier-Stokes

text: equations.

text: J.

text: Comput.

text: Phys.,

text: Matthew

text: Brand.

text: Fast

text: low-rank

text: modiﬁcations

text: of

text: the

text: thin

text: singular

text: value

text: decomposition.

text: Linear

text: Algebra

text: Appl.,

text: Tan

text: Bui-Thanh.

text: Construction

text: and

text: analysis

text: of

text: HDG

text: methods

text: for

text: linearized

text: shallow

text: water

text: equations.

text: SIAM

text: J.

text: Sci.

text: Comput.,

text: Paul

text: Castillo,

text: Bernardo

text: Cockburn,

text: Ilaria

text: Perugia,

text: and

text: Dominik

text: Sch¨otzau.

text: An

text: a

text: priori

text: error

text: analysis

text: of

text: the

text: local

text: discontinuous

text: Galerkin

text: method

text: for

text: elliptic

text: problems.

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: Brandon

text: Chabaud

text: and

text: Bernardo

text: Cockburn.

text: Uniform-in-time

text: superconvergence

text: of

text: HDG

text: meth-

text: ods

text: for

text: the

text: heat

text: equation.

text: Math.

text: Comp.,

text: D.

text: Chapelle,

text: A.

text: Gariah,

text: P.

text: Moireau,

text: and

text: J.

text: Sainte-Marie.

text: A

text: Galerkin

text: strategy

text: with

text: proper

text: orthogonal

text: decomposition

text: for

text: parameter-dependent

text: problems—analysis,

text: assessments

text: and

text: ap-

text: plications

text: to

text: parameter

text: estimation.

text: ESAIM

text: Math.

text: Model.

text: Numer.

text: Anal.,

text: Dominique

text: Chapelle,

text: Asven

text: Gariah,

text: and

text: Jacques

text: Sainte-Marie.

text: Galerkin

text: approximation

text: with

text: proper

text: orthogonal

text: decomposition:

text: new

text: error

text: estimates

text: and

text: illustrative

text: examples.

text: ESAIM

text: Math.

text: Model.

text: Numer.

text: Anal.,

text: Bernardo

text: Cockburn,

text: Bo

text: Dong,

text: Johnny

text: Guzm´an,

text: Marco

text: Restelli,

text: and

text: Riccardo

text: Sacco.

text: A

text: hy-

text: bridizable

text: discontinuous

text: Galerkin

text: method

text: for

text: steady-state

text: convection-diﬀusion-reaction

text: prob-

text: lems.

text: SIAM

text: J.

text: Sci.

text: Comput.,

text: Bernardo

text: Cockburn,

text: Jayadeep

text: Gopalakrishnan,

text: and

text: Raytcho

text: Lazarov.

text: Uniﬁed

text: hybridization

text: of

text: discontinuous

text: Galerkin,

text: mixed,

text: and

text: continuous

text: Galerkin

text: methods

text: for

text: second

text: order

text: elliptic

text: problems.

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: Bernardo

text: Cockburn

text: and

text: Chi-Wang

text: Shu.

text: The

text: local

text: discontinuous

text: Galerkin

text: method

text: for

text: time-

text: dependent

text: convection-diﬀusion

text: systems.

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: Jintao

text: Cui

text: and

text: Wujun

text: Zhang.

text: An

text: analysis

text: of

text: HDG

text: methods

text: for

text: the

text: Helmholtz

text: equation.

text: IMA

text: J.

text: Numer.

text: Anal.,

text: Hiba

text: Fareed,

text: Jiguang

text: Shen,

text: John

text: R.

text: Singler,

text: and

text: Yangwen

text: Zhang.

text: Incremental

text: proper

text: orthog-

text: onal

text: decomposition

text: for

text: PDE

text: simulation

text: data.

text: Computers

text: Mathematics

text: with

text: Applications.

text: to

text: appear.

text: Pedro

text: Gal´an

text: del

text: Sastre

text: and

text: Rodolfo

text: Bermejo.

text: Error

text: estimates

text: of

text: proper

text: orthogonal

text: decom-

text: position

text: eigenvectors

text: and

text: Galerkin

text: projection

text: for

text: a

text: general

text: dynamical

text: system

text: arising

text: in

text: ﬂuid

text: models.

text: Numer.

text: Math.,

text: Gabriel

text: N.

text: Gatica

text: and

text: Fil´ander

text: A.

text: Sequeira.

text: A

text: priori

text: and

text: a

text: posteriori

text: error

text: analyses

text: of

text: an

text: aug-

text: mented

text: HDG

text: method

text: for

text: a

text: class

text: of

text: quasi-Newtonian

text: Stokes

text: ﬂows.

text: J.

text: Sci.

text: Comput.,


text: (cid:98) − ∇ · (cid:104) (cid:98) · (cid:105) (cq , v)T (u , v)T + u , v n T = 0, (14a) r ∇h · r (cid:104)h (cid:98)−r (cid:105)∂ h (∂ u , w)T + ( q , w)T + τ(u u ), w T = (f, w)T , (14b) t r h (cid:104) r · h −r r (cid:105) ∂ h h q n + τ(u u ), µ T \ = 0, (14c) r r r ∂ ε∂ h· h u ( , 0) = u . (14d) r r,0 (cid:98) The system (14) is a r(cid:98)educed model but not our ﬁnal reduced order model since it has three variables q , u , and u . We utilize (14a) and (14c) to eliminate the reduced ﬂux and numerical r r r ∈ × trace as follows: let (qur, uur) V r1 Mr3 be the unique solution of r r h h (cid:98) (cid:104) (cid:98) · (cid:105) ∇ · (cqur, v)T + uur, v n T = (u , v)T , (15a) (cid:104)−r · h r (cid:105) ∂ h (cid:104) r (cid:105) h qur n + τuur, µ T \ = τu , µ T \ , (15b) r r ∂ ε∂ r ∂ ε∂ h h h h (cid:98) ∈ × for all (v, µ) V r1 Mr3. The system (15) is uniquely solvable since the bilinear form on the h h × ∈ left hand side is positive deﬁnite on V r1 Mr3. In general, for w W r2 we deﬁne (qw, uw) to be h h h r r the unique solution of (cid:98) (cid:104) (cid:98) · (cid:105) ∇ · (cqw, v)T + uw, v n T = (w, v)T , (16a) (cid:104)−r · h r (cid:105) ∂ h (cid:104) (cid:105) h qw n + τuw, µ T \ = τw, µ T \ . (16b) r r ∂ ε∂ ∂ ε∂ h h h h This allows us to rewrite the reduced order model. ∈ Theorem 1. The HDG-POD reduced order model (14) can be rewritten as follows: ﬁnd u W r2 r h satisfying (∂ u , w)T + a (u , w) = (cid:96) (w), (17a) t r r r r h · u ( , 0) = u , (17b) r r,0 ∈ for all w W r2. Here, the forms are given by h (cid:98) (cid:98) (cid:104) − − (cid:105) a (u , w) = (cqur, qw)T + τ(u uur), w uw T , (18) r r r r h r r r ∂ h (cid:96) (w) = (f, w)T , (19) r h ∈ for u , w W r2. Also, the bilinear form a deﬁned on W r2 is symmetric and semipositive r h r h deﬁnite. Proof. First, from (14b) we have (cid:98) ∇ · (cid:104) − (cid:105) (f, w)T = (∂ u , w)T + ( q , w)T + τ(u u ), w T . h t r h r h r r ∂ h 9

label: equation

text: (cq

text: v)T

text: (u

text: v)T

text: u

text: v

text: n

text: T

text: r

text: ∇h

text: r

text: h

text: u

text: w)T

text: q

text: w)T

text: τ(u

text: u

text: w

text: T

text: (f,

text: w)T

text: t

text: r

text: h

text: r

text: h

text: −r

text: r

text: h

text: h

text: q

text: n

text: τ(u

text: u

text: µ

text: T

text: r

text: r

text: r

text: ε∂

text: h·

text: h

text: u

text: u

text: r

text: The

text: system

text: is

text: a

text: model

text: but

text: not

text: our

text: ﬁnal

text: reduced

text: order

text: model

text: since

text: it

text: has

text: three

text: variables

text: q

text: u

text: and

text: u

text: We

text: utilize

text: and

text: to

text: eliminate

text: the

text: reduced

text: ﬂux

text: and

text: numerical

text: r

text: r

text: r

text: trace

text: as

text: follows:

text: let

text: (qur,

text: uur)

text: V

text: be

text: the

text: unique

text: solution

text: of

text: r

text: r

text: h

text: h

text: (cqur,

text: v)T

text: uur,

text: v

text: n

text: T

text: (u

text: v)T

text: h

text: r

text: h

text: r

text: h

text: qur

text: n

text: τuur,

text: µ

text: T

text: τu

text: µ

text: T

text: r

text: r

text: ε∂

text: r

text: ε∂

text: h

text: h

text: h

text: h

text: for

text: all

text: (v,

text: µ)

text: V

text: The

text: system

text: is

text: uniquely

text: solvable

text: since

text: the

text: bilinear

text: form

text: on

text: the

text: h

text: h

text: left

text: hand

text: side

text: is

text: positive

text: deﬁnite

text: on

text: V

text: In

text: general,

text: for

text: w

text: W

text: we

text: deﬁne

text: (qw,

text: uw)

text: to

text: be

text: h

text: h

text: h

text: r

text: r

text: the

text: unique

text: solution

text: of

text: (cqw,

text: v)T

text: uw,

text: v

text: n

text: T

text: (w,

text: v)T

text: h

text: r

text: h

text: h

text: qw

text: n

text: τuw,

text: µ

text: T

text: τw,

text: µ

text: T

text: r

text: r

text: ε∂

text: ε∂

text: h

text: h

text: h

text: h

text: This

text: allows

text: us

text: to

text: rewrite

text: the

text: reduced

text: order

text: model.

text: Theorem

text: The

text: HDG-POD

text: reduced

text: order

text: model

text: can

text: be

text: rewritten

text: as

text: follows:

text: ﬁnd

text: u

text: W

text: r

text: h

text: satisfying

text: u

text: w)T

text: a

text: (u

text: w)

text: (w),

text: t

text: r

text: r

text: r

text: r

text: h

text: u

text: u

text: r

text: for

text: all

text: w

text: W

text: Here,

text: the

text: forms

text: are

text: given

text: by

text: h

text: a

text: (u

text: w)

text: (cqur,

text: qw)T

text: τ(u

text: uur),

text: w

text: uw

text: T

text: r

text: r

text: r

text: r

text: h

text: r

text: r

text: r

text: h

text: (w)

text: (f,

text: w)T

text: r

text: h

text: for

text: u

text: w

text: W

text: Also,

text: the

text: bilinear

text: form

text: a

text: deﬁned

text: on

text: W

text: is

text: symmetric

text: and

text: semipositive

text: r

text: h

text: r

text: h

text: deﬁnite.

text: Proof.

text: First,

text: from

text: we

text: have

text: (f,

text: w)T

text: u

text: w)T

text: q

text: w)T

text: τ(u

text: u

text: w

text: T

text: h

text: t

text: r

text: h

text: r

text: h

text: r

text: r

text: h