Randomness-efficient curve sampling

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m log_q(1/δ))^O(1) in F_q^m. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

Efficient shock capturing for isentropic flows using arithmetic averaging

A shock capturing scheme is presented for the equations of isentropic flow based on upwind differencing applied to a locally linearized set of Riemann problems. This includes the two-dimensional shallow water equations using the familiar gas dynamics analogy. An average of the flow variables across the interface between cells is required, and this average is chosen to be the arithmetic mean for computational efficiency, leading to arithmetic averaging. This is in contrast to usual ‘square root’ averages found in this type of Riemann solver where the computational expense can be prohibitive. The scheme is applied to a two-dimensional dam-break problem and the approximate solution compares well with those given by other authors.

An efficient numerical method for compressible flows of a real gas using arithmetic averaging

An efficient numerical method is presented for the solution of the Euler equations governing the compressible flow of a real gas. The scheme is based on the approximate solution of a specially constructed set of linearised Riemann problems. An average of the flow variables across the interface between cells is required, and this is chosen to be the arithmetic mean for computational efficiency, which is in contrast to the usual square root averaging. The scheme is applied to a test problem for five different equations of state.

An efficient numerical scheme for the two-dimensional shallow water equations using arithmetic averaging

A finite difference scheme based on flux difference splitting is presented for the solution of the two-dimensional shallow water equations of ideal fluid flow. A linearised problem, analogous to that of Riemann for gas dynamics is defined, and a scheme, based on numerical characteristic decomposition is presented for obtaining approximate solutions to the linearised problem, and incorporates the technique of operator splitting. An average of the flow variables across the interface between cells is required, and this average is chosen to be the arithmetic mean for computational efficiency leading to arithmetic averaging. This is in contrast to usual ‘square root’ averages found in this type of Riemann solver, where the computational expense can be prohibitive. The method of upwind differencing is used for the resulting scalar problems, together with a flux limiter for obtaining a second order scheme which avoids nonphysical, spurious oscillations. An extension to the two-dimensional equations with source terms is included. The scheme is applied to the one-dimensional problems of a breaking dam and reflection of a bore, and in each case the approximate solution is compared to the exact solution of ideal fluid flow. The scheme is also applied to a problem of stationary bore generation in a channel of variable cross-section. Finally, the scheme is applied to two other dam-break problems, this time in two dimensions with one having cylindrical symmetry. Each approximate solution compares well with those given by other authors.

Faster pairings on special Weierstrass curves

This paper presents efficient formulas for computing cryptographic pairings on the curve y 2 = c x 3 + 1 over fields of large characteristic. We provide examples of pairing-friendly elliptic curves of this form which are of interest for efficient pairing implementations.

An efficient DSE using conditional multivariate complex Gaussian distribution

This paper presents an efficient noniterative method for distribution state estimation using conditional multivariate complex Gaussian distribution (CMCGD). In the proposed method, the mean and standard deviation (SD) of the state variables is obtained in one step considering load uncertainties, measurement errors, and load correlations. In this method, first the bus voltages, branch currents, and injection currents are represented by MCGD using direct load flow and a linear transformation. Then, the mean and SD of bus voltages, or other states, are calculated using CMCGD and estimation of variance method. The mean and SD of pseudo measurements, as well as spatial correlations between pseudo measurements, are modeled based on the historical data for different levels of load duration curve. The proposed method can handle load uncertainties without using time-consuming approaches such as Monte Carlo. Simulation results of two case studies, six-bus, and a realistic 747-bus distribution network show the effectiveness of the proposed method in terms of speed, accuracy, and quality against the conventional approach.

Numerical studies on quasilinear and linear elliptic equations

We explore here the acceleration of convergence of iterative methods for the solution of a class of quasilinear and linear algebraic equations. The specific systems are the finite difference form of the Navier-Stokes equations and the energy equation for recirculating flows. The acceleration procedures considered are: the successive over relaxation scheme; several implicit methods; and a second-order procedure. A new implicit method—the alternating direction line iterative method—is proposed in this paper. The method combines the advantages of the line successive over relaxation and alternating direction implicit methods. The various methods are tested for their computational economy and accuracy on a typical recirculating flow situation. The numerical experiments show that the alternating direction line iterative method is the most economical method of solving the Navier-Stokes equations for all Reynolds numbers in the laminar regime. The usual ADI method is shown to be not so attractive for large Reynolds numbers because of the loss of diagonal dominance. This loss can however be restored by a suitable choice of the relaxation parameter, but at the cost of accuracy. The accuracy of the new procedure is comparable to that of the well-tested successive overrelaxation method and to the available results in the literature. The second-order procedure turns out to be the most efficient method for the solution of the linear energy equation.

Two-Phase Thermodynamic Model for Efficient and Accurate Absolute Entropy of Water from Molecular Dynamics Simulations

Presented here is the two-phase thermodynamic (2PT) model for the calculation of energy and entropy of molecular fluids from the trajectory of molecular dynamics (MD) simulations. In this method, the density of state (DoS) functions (including the normal modes of translation, rotation, and intramolecular vibration motions) are determined from the Fourier transform of the corresponding velocity autocorrelation functions. A fluidicity parameter (f), extracted from the thermodynamic state of the system derived from the same MD, is used to partition the translation and rotation modes into a diffusive, gas-like component (with 3Nf degrees of freedom) and a nondiffusive, solid-like component. The thermodynamic properties, including the absolute value of entropy, are then obtained by applying quantum statistics to the solid component and applying hard sphere/rigid rotor thermodynamics to the gas component. The 2PT method produces exact thermodynamic properties of the system in two limiting states: the nondiffusive solid state (where the fluidicity is zero) and the ideal gas state (where the fluidicity becomes unity). We examine the 2PT entropy for various water models (F3C, SPC, SPC/E, TIP3P, and TIP4P-Ew) at ambient conditions and find good agreement with literature results obtained based on other simulation techniques. We also validate the entropy of water in the liquid and vapor phases along the vapor-liquid equilibrium curve from the triple point to the critical point. We show that this method produces converged liquid phase entropy in tens of picoseconds, making it an efficient means for extracting thermodynamic properties from MD simulations.

Methods and applications for improving parameter prediction models for stand structures in Finland

This thesis report attempts to improve the models for predicting forest stand structure for practical use, e.g. forest management planning (FMP) purposes in Finland. Comparisons were made between Weibull and Johnson s SB distribution and alternative regression estimation methods. Data used for preliminary studies was local but the final models were based on representative data. Models were validated mainly in terms of bias and RMSE in the main stand characteristics (e.g. volume) using independent data. The bivariate SBB distribution model was used to mimic realistic variations in tree dimensions by including within-diameter-class height variation. Using the traditional method, diameter distribution with the expected height resulted in reduced height variation, whereas the alternative bivariate method utilized the error-term of the height model. The lack of models for FMP was covered to some extent by the models for peatland and juvenile stands. The validation of these models showed that the more sophisticated regression estimation methods provided slightly improved accuracy. A flexible prediction and application for stand structure consisted of seemingly unrelated regression models for eight stand characteristics, the parameters of three optional distributions and Näslund s height curve. The cross-model covariance structure was used for linear prediction application, in which the expected values of the models were calibrated with the known stand characteristics. This provided a framework to validate the optional distributions and the optional set of stand characteristics. Height distribution is recommended for the earliest state of stands because of its continuous feature. From the mean height of about 4 m, Weibull dbh-frequency distribution is recommended in young stands if the input variables consist of arithmetic stand characteristics. In advanced stands, basal area-dbh distribution models are recommended. Näslund s height curve proved useful. Some efficient transformations of stand characteristics are introduced, e.g. the shape index, which combined the basal area, the stem number and the median diameter. Shape index enabled SB model for peatland stands to detect large variation in stand densities. This model also demonstrated reasonable behaviour for stands in mineral soils.

Free convection about cylinders of elliptic cross section embedded in a porous medium

Numerical solutions are presented for the free convection boundary layers over cylinders of elliptic cross section embedded in a fluid-saturated porous medium. The transformed conservation equations of the nonsimilar boundary layers are solved numerically by an efficient finite-difference method. The theory was applied to a number of cylinders and the results compared very well with published analytical solutions. The results are of use in the design of underground electrical cables, power plant steam, and water distribution lines, among others.

Efficient statistical modeling for the compression of tree structured intermediate code

We propose a scheme for the compression of tree structured intermediate code consisting of a sequence of trees specified by a regular tree grammar. The scheme is based on arithmetic coding, and the model that works in conjunction with the coder is automatically generated from the syntactical specification of the tree language. Experiments on data sets consisting of intermediate code trees yield compression ratios ranging from 2.5 to 8, for file sizes ranging from 167 bytes to 1 megabyte.

A LSQR-type method provides a computationally efficient automated optimal choice of regularization parameter in diffuse optical tomography

Purpose: Developing a computationally efficient automated method for the optimal choice of regularization parameter in diffuse optical tomography. Methods: The least-squares QR (LSQR)-type method that uses Lanczos bidiagonalization is known to be computationally efficient in performing the reconstruction procedure in diffuse optical tomography. The same is effectively deployed via an optimization procedure that uses the simplex method to find the optimal regularization parameter. The proposed LSQR-type method is compared with the traditional methods such as L-curve, generalized cross-validation (GCV), and recently proposed minimal residual method (MRM)-based choice of regularization parameter using numerical and experimental phantom data. Results: The results indicate that the proposed LSQR-type and MRM-based methods performance in terms of reconstructed image quality is similar and superior compared to L-curve and GCV-based methods. The proposed method computational complexity is at least five times lower compared to MRM-based method, making it an optimal technique. Conclusions: The LSQR-type method was able to overcome the inherent limitation of computationally expensive nature of MRM-based automated way finding the optimal regularization parameter in diffuse optical tomographic imaging, making this method more suitable to be deployed in real-time. (C) 2013 American Association of Physicists in Medicine. http://dx.doi.org/10.1118/1.4792459]

A FRAMEWORK FOR THE ERROR ANALYSIS OF DISCONTINUOUS FINITE ELEMENT METHODS FOR ELLIPTIC OPTIMAL CONTROL PROBLEMS AND APPLICATIONS TO C-0 IP METHODS

In this article, an abstract framework for the error analysis of discontinuous Galerkin methods for control constrained optimal control problems is developed. The analysis establishes the best approximation result from a priori analysis point of view and delivers a reliable and efficient a posteriori error estimator. The results are applicable to a variety of problems just under the minimal regularity possessed by the well-posedness of the problem. Subsequently, the applications of C-0 interior penalty methods for a boundary control problem as well as a distributed control problem governed by the biharmonic equation subject to simply supported boundary conditions are discussed through the abstract analysis. Numerical experiments illustrate the theoretical findings.

Efficient simulation and rendering of realistic motion of one-dimensional flexible objects

In gross motion of flexible one-dimensional (1D) objects such as cables, ropes, chains, ribbons and hair, the assumption of constant length is realistic and reasonable. The motion of the object also appears more natural if the motion or disturbance given at one end attenuates along the length of the object. In an earlier work, variational calculus was used to derive natural and length-preserving transformation of planar and spatial curves and implemented for flexible 1D objects discretized with a large number of straight segments. This paper proposes a novel idea to reduce computational effort and enable real-time and realistic simulation of the motion of flexible 1D objects. The key idea is to represent the flexible 1D object as a spline and move the underlying control polygon with much smaller number of segments. To preserve the length of the curve to within a prescribed tolerance as the control polygon is moved, the control polygon is adaptively modified by subdivision and merging. New theoretical results relating the length of the curve and the angle between the adjacent segments of the control polygon are derived for quadratic and cubic splines. Depending on the prescribed tolerance on length error, the theoretical results are used to obtain threshold angles for subdivision and merging. Simulation results for arbitrarily chosen planar and spatial curves whose one end is subjected to generic input motions are provided to illustrate the approach. (C) 2016 Elsevier Ltd. All rights reserved.