Physical Sciences and Mathematics Commons^™

Capturing Data Uncertainty In Highvolume Stream Processing, Yanlei Diao, Boduo Li, Anna Liu, Liping Peng, Charles Sutton, Thanh Tran, Michael Zink

Yanlei Diao

We present the design and development of a data stream system that captures data uncertainty from data collection to query processing to final result generation. Our system focuses on data that is naturally modeled as continuous random variables such as many types of sensor data. To provide an end-to-end solution, our system employs probabilistic modeling and inference to generate uncertainty description for raw data, and then a suite of statistical techniques to capture changes of uncertainty as data propagates through query operators. To cope with high-volume streams, we explore advanced approximation techniques for both space and time efficiency. We are …

The Hamiltonian Index Of Graphs, Yi Hong, Jian-Liang Lin, Zhi-Sui Tao, Zhi-Hong Chen

Zhi-Hong Chen

The Hamiltonian index of a graph G is defined as h ( G ) = min { m : L m ( G ) is Hamiltonian } . In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph H ̃ ( m ) ( G ) from G and prove that if h ( G ) ≥ 2 , then h ( G ) = min{ m : H ̃ ( m ) ( G ) has a spanning Eulerian subgraph …

Wavelet-Based Bayesian Estimation Of Partially Linear Regression Models With Long Memory Errors, Kyungduk Ko, Leming Qu, Marina Vannucci

Kyungduk Ko

In this paper we focus on partially linear regression models with long memory errors, and propose a wavelet-based Bayesian procedure that allows the simultaneous estimation of the model parameters and the nonparametric part of the model. Employing discrete wavelet transforms is crucial in order to simplify the dense variance-covariance matrix of the long memory error. We achieve a fully Bayesian inference by adopting a Metropolis algorithm within a Gibbs sampler. We evaluate the performances of the proposed method on simulated data. In addition, we present an application to Northern hemisphere temperature data, a benchmark in the long memory literature.

Africa In The World Trade Network, Luca De Benedictis

Luca De Benedictis

Accuracy, Resolution And Stability Properties Of A Modified Chebyshev Method, Jodi Mead, Rosemary A. Renaut

Jodi Mead

While the Chebyshev pseudospectral method provides a spectrally accurate method, integration of partial differential equations with spatial derivatives of order M requires time steps of approximately O(N−2M) for stable explicit solvers. Theoretically, time steps may be increased to O(N−M) with the use of a parameter, α-dependent mapped method introduced by Kosloff and Tal-Ezer [ J. Comput. Phys., 104 (1993), pp. 457–469]. Our analysis focuses on the utilization of this method for reasonable practical choices for N, namely N ≲ 30, as may be needed for two- or three dimensional modeling. Results presented confirm that spectral accuracy with increasing N is …

Boundary Type Quadrature Formulas Over Axially Symmetric Regions, Tian-Xiao He

Tian-Xiao He

A boundary type quadrature formula (BTQF) is an approximate integration formula with all its of evaluation points lying on the Boundary of the integration domain. This type formulas are particularly useful for the cases when the values of the integrand functions and their derivatives inside the domain are not given or are not easily determined. In this paper, we will establish the BTQFs over sonic axially symmetric regions. We will discuss time following three questions in the construction of BTQFs: (i) What is the highest possible degree of algebraic precision of the BTQF if it exists? (ii) What is the …

The Hamiltonian Index Of Graphs, Zhi-Hong Chen, Yi Hong, Jian-Liang Lin, Zhi-Sui Tao

Zhi-Hong Chen

The Hamiltonian index of a graph GG is defined as h(G)=min{m:Lm(G) is Hamiltonian}.h(G)=min{m:Lm(G) is Hamiltonian}. In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph sourceH̃^(m)(G) from GG and prove that if h(G)≥2h(G)≥2, then h(G) = min{m : H̃^(m)(G) has a spanning Eulerian subgraph}.

Spanning Eulerian Subgraphs In Claw-Free Graphs, Zhi-Hong Chen, Hong-Jian Lai, Weiqi Luo, Yehomg Shao

Zhi-Hong Chen

A graph is claw-free if it has no induced K 1,3, subgraph. A graph is essential 4-edge-connected if removing at most three edges, the resulting graph has at most one component having edges. In this note, we show that every essential 4-edge-connected claw free graph has a spanning Eulerian subgraph with maximum degree at most 4.

Spanning Trails Containing Given Edges, Weiqi Luo, Zhi-Hong Chen, Wei-Guo Chen

Zhi-Hong Chen

A graph G is Eulerian-connected if for any u and v in V ( G ) , G has a spanning ( u , v ) -trail. A graph G is edge-Eulerian-connected if for any e ′ and e ″ in E ( G ) , G has a spanning ( e ′ , e ″ ) -trail. For an integer r ⩾ 0 , a graph is called r -Eulerian-connected if for any X ⊆ E ( G ) with | X | ⩽ r , and for any u , v ∈ V ( G ) , G …

Collapsible Graphs And Reductions Of Line Graphs, Zhi-Hong Chen, Peter C.B. Lam, Wai-Chee Shiu

Zhi-Hong Chen

A graph G is collapsible if for every even subset X ⊆ V ( G ) , G has a subgraph such that G − E ( Γ ) is connected and the set of odd-degree vertices of Γ is X . A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G . In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. …

The Shallow Water Equations In Lagrangian Coordinates, J. L. Mead

Jodi Mead

Recent advances in the collection of Lagrangian data from the ocean and results about the well-posedness of the primitive equations have led to a renewed interest in solving flow equations in Lagrangian coordinates. We do not take the view that solving in Lagrangian coordinates equates to solving on a moving grid that can become twisted or distorted. Rather, the grid in Lagrangian coordinates represents the initial position of particles, and it does not change with time. However, using Lagrangian coordinates results in solving a highly nonlinear partial differential equation. The nonlinearity is mainly due to the Jacobian of the coordinate …

Towards Regional Assimilation Of Lagrangian Data: The Lagrangian Form Of The Shallow Water Reduced Gravity Model And Its Inverse, J. L. Mead, A. F. Bennett

Jodi Mead

Variational data assimilation for Lagrangian geophysical fluid dynamics is introduced. Lagrangian coordinates add numerical difficulties into an already difficult subject, but also offer certain distinct advantages over Eulerian coordinates. First, float position and depth are defined by linear measurement functionals. Second, Lagrangian or ‘comoving’ open domains are conveniently expressed in Lagrangian coordinates. The attraction of such open domains is that they lead to well-posed prediction problems [Bennett and Chua (1999)] and hence efficient inversion algorithms. Eulerian and Lagrangian solutions of the inviscid forward problem in a doubly periodic domain, with North Atlantic mesoscales, are compared and found to be in …

An Iterated Pseudospectral Method For Functional Partial Differential Equations, J. Mead, B. Zubik-Kowal

Jodi Mead

Chebyshev pseudospectral spatial discretization preconditioned by the Kosloff and Tal-Ezer transformation [10] is applied to hyperbolic and parabolic functional equations. A Jacobi waveform relaxation method is then applied to the resulting semi-discrete functional systems, and the result is a simple system of ordinary differential equations d/dtUk+1(t) = MαUk+1(t)+f(t,U kt). Here Mα is a diagonal matrix, k is the index of waveform relaxation iterations, U kt is a functional argument computed from the previous iterate and the function f, like the matrix Mα, depends on the process of semi-discretization. This waveform relaxation splitting has the advantage of straight forward, direct application …

Assimilation Of Simulated Float Data In Lagrangian Coordinates, J. L. Mead

Jodi Mead

We implement an approach for the accurate assimilation of Lagrangian data into regional general ocean circulation models. The forward model is expressed in Lagrangian coordinates and simulated float data are incorporated into the model via four dimensional variational data assimilation. We show that forward solutions computed in Lagrangian coordinates are reliable for time periods of up to 100 days with phase speeds of 1 m/s and deformation radius of 35 km. The position and depth of simulated floats are assimilated into the viscous, Lagrangian shallow water equations. The weights for the errors in the model and data are varied and …

The 1905 Einstein Equation In A General Mathematical Analysis Model Of Quasars, Byron E. Bell

Byron E. Bell

Least Squares Problems With Inequality Constraints As Quadratic Constraints, Jodi Mead, Rosemary A. Renaut

Jodi Mead

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution.

The effectiveness of the proposed algorithm is investigated through solving three …

A Newton Root-Finding Algorithm For Estimating The Regularization Parameter For Solving Ill-Conditioned Least Squares Problems, Jodi Mead, Rosemary Renaut

Jodi Mead

We discuss the solution of numerically ill-posed overdetermined systems of equations using Tikhonov a-priori-based regularization. When the noise distribution on the measured data is available to appropriately weight the fidelity term, and the regularization is assumed to be weighted by inverse covariance information on the model parameters, the underlying cost functional becomes a random variable that follows a X2 distribution. The regularization parameter can then be found so that the optimal cost functional has this property. Under this premise a scalar Newton root-finding algorithm for obtaining the regularization parameter is presented. The algorithm, which uses the singular value decomposition of …

Regressive Functions On Pairs, Andrés Eduardo Caicedo

Andrés E. Caicedo

We compute an explicit upper bound for the regressive Ramsey numbers by a combinatorial argument, the corresponding function being of Ackermannian growth. For this, we look at the more general problem of bounding g(n, m), the least l such that any regressive function ƒ: [m, l][2]→ℕ admits a min-homogeneous set of size n. Analysis of this function also leads to the simplest known proof that the regressive Ramsey numbers have rate of growth at least Ackermannian. Together, these results give a purely combinatorial proof that, for each m, g(·, m) has rate of growth precisely Ackermannian, considerably improve the previously …

From Euler To Witten: A Short Survey Of The Volume Conjecture In Knot Theory, Uwe Kaiser

Uwe Kaiser

No abstract provided.

Exponential Growth Rate Of Paths And Its Connection With Dynamics, Pengfei Zhang

Pengfei Zhang

No abstract provided.

When Does A Category Built On A Lattice With A Monoidal Structure Have A Monoidal Structure?, Lawrence Stout

Lawrence N. Stout

In a word, sometimes. And it gets harder if the structure on L is not commutative. In this paper we consider the question of what properties are needed on the lattice L equipped with an operation * for several different kinds of categories built using Sets and L to have monoidal and monoidal closed structures. This works best for the Goguen category Set(L) in which membership, but not equality, is made fuzzy and maps respect membership. Commutativity becomes critical if we make the equality fuzzy as well. This can be done several ways, so a progression of categories is considered. …

Categorical Approaches To Non-Commutative Fuzzy Logic, Lawrence Stout

Lawrence N. Stout

In this paper we consider what it means for a logic to be non-commutative, how to generate examples of structures with a non-commutative operation * which have enough nice properties to serve as the truth values for a logic. Inference in the propositional logic is gotten from the categorical properties (products, coproducts, monoidal and closed structures, adjoint functors) of the categories of truth values. We then show how to extend this view of propositional logic to a predicate logic using categories of propositions about a type A with functors giving change of type and adjoints giving quantifiers. In the case …

A Categorical Semantics For Fuzzy Predicate Logic, Lawrence N. Stout

Lawrence N. Stout

The object of this study is to look at categorical approaches to many valued logic, both propositional and predicate, to see how different logical properties result from different parts of the situation. In particular, the relationship between the categorical fabric I introduced at Linz in 2004 and the Fuzzy Logics studied by Hajek (2003) [5], Esteva et al. (2003) [1], and Hajek (1998) [4], comes from restricting the kind of structures used for truth values. We see how the structure of the various kinds of algebras shows up in the categorical logic, giving a variant on natural deduction for these …

Spectral Decomposition Of Kac-Murdock-Szego Matrices, William F. Trench

William F. Trench

No abstract provided.