Narrow Results

We analyze the parallel performance of randomized interpolative decomposition by decomposing low rank complex-valued Gaussian random matrices of about 100 GB. We chose a Cray XMT supercomputer as it provides an almost ideal PRAM model permitting quick investigation of parallel algorithms without obfuscation from hardware idiosyncrasies. We obtain that on non-square matrices performance scales almost linearly with runtime about 100 times faster on 128 processors. We also verify that numerically discovered error bounds still hold on matrices two orders of magnitude larger than those previously tested.

Ensemble learning systems could lower down the risk of overfitting that often appears in a single learning model. Different to those ensemble learning approaches by re-sampling, negative correlation learning trains all learners in an ensemble simultaneously and cooperatively. However, overfitting had sometimes been observed in negative correlation learning. Two error bounds are therefore introduced into negative correlation learning for preventing overfitting. One is the upper bound of error output (UBEO) which divides the training data into two groups based on the distances between the data and the formed decision boundary. The other is the lower bound of error rate (LBER) which is set as a learning switch. Before the performance measured by error rates is higher than LBER, negative correlation learning is applied on the whole training set. As soon as the performance is lower than LBER, negative correlation learning will only be applied to the group of data whose distances to the current decision boundary are within the range of UBEO. The other group of data outside of this range will not be learned anymore. Further learning on the data points in the later group would make the learned decision boundary too complex to classify the unseen data well. Experimental results would explore how LBER and UBEO would lead negative correlation learning towards a robust decision boundary.

We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each simplification operation and use this function to measure deviation of the new surface from both the previous level of detail and from the original surface. In addition, we use the mapping function to compute appropriate texture coordinates if the original model has texture coordinates at its vertices. Our overall algorithm uses edge collapse operations. We present rigorous procedures for the generation of local orthogonal projections to the plane as well as for the selection of a new vertex position resulting from the edge collapse operation. The algorithm computes guaranteed error bounds on surface deviation and produces an entire continuum of levels of detail with mappings between them. We demonstrate the effectiveness of our algorithm on several models: a Ford Bronco consisting of over 300 parts and 70, 000 triangles, a textured lion model consisting of 49 parts and 86, 000 triangles, a textured, wrinkled torus consisting of 79, 000 triangles, a dragon model consisting of 871, 000 triangles, a Buddha model consisting of 1,000,000 triangles, and an armadillo model consisting of 2, 000, 000 triangles.

The bisector of two plane curve segments (other than lines and circles) has, in general, no simple — i.e., rational — parameterization, and must therefore be approximated by the interpolation of discrete data. A procedure for computing ordered sequences of point/tangent/curvature data along the bisectors of polynomial or rational plane curves is described, with special emphasis on (i) the identification of singularities (tangent–discontinuities) of the bisector; (ii) capturing the exact rational form of those portions of the bisector with a terminal footpoint on one curve; and (iii) geometrical criteria the characterize extrema of the distance error for interpolants to the discretely–sample data. G¹ piecewise– parabolic and G² piecewise–cubic approximations (with O(h⁴) and O(h⁶) convergence) are described which, used in adaptive schemes governed by the exact error measure, can be made to satisfy any prescribed geometrical tolerance.

In this paper, a method for deriving computable estimates of the approximation error in eigenvalues or eigenfrequencies of three-dimensional linear elasticity or shell problems is presented. The analysis for the error estimator follows the general approach of goal-oriented error estimation for which the error is estimated in so-called quantities of interest, here the eigenfrequencies, rather than global norms. A general theory is developed and is then applied to the linear elasticity equations. For the shell analysis, it is assumed that the shell model is not completely known and additional errors are introduced due to modeling approximations. The approach is then based on recovering three-dimensional approximations from the shell eigensolution and employing the error estimator developed for linear elasticity. The performance of the error estimator is demonstrated on several test problems.

In this paper we present reduced basis (RB) approximations and associated rigorous a posteriori error bounds for the parametrized unsteady Boussinesq equations. The essential ingredients are Galerkin projection onto a low-dimensional space associated with a smooth parametric manifold — to provide dimension reduction; an efficient proper orthogonal decomposition–Greedy sampling method for identification of optimal and numerically stable approximations — to yield rapid convergence; accurate (online) calculation of the solution-dependent stability factor by the successive constraint method — to quantify the growth of perturbations/residuals in time; rigorous a posteriori bounds for the errors in the RB approximation and associated outputs — to provide certainty in our predictions; and an offline–online computational decomposition strategy for our RB approximation and associated error bound — to minimize marginal cost and hence achieve high performance in the real-time and many-query contexts. The method is applied to a transient natural convection problem in a two-dimensional "complex" enclosure — a square with a small rectangle cutout — parametrized by Grashof number and orientation with respect to gravity. Numerical results indicate that the RB approximation converges rapidly and that furthermore the (inexpensive) rigorous a posteriori error bounds remain practicable for parameter domains and final times of physical interest.

We present reduced basis approximations and associated rigorous a posteriori error bounds for the Stokes equations in parametrized domains. The method, built upon the penalty formulation for saddle point problems, provides error bounds not only for the velocity but also for the pressure approximation, while simultaneously admitting affine geometric variations with relative ease. The essential ingredients are: (i) dimension reduction through Galerkin projection onto a low-dimensional reduced basis space; (ii) stable, good approximation of the pressure through supremizer-enrichment of the velocity reduced basis space; (iii) optimal and numerically stable approximations identified through an efficient greedy sampling method; (iv) certainty, through rigorous a posteriori bounds for the errors in the reduced basis approximation; and (v) efficiency, through an offline-online computational strategy. The method is applied to a flow problem in a two-dimensional channel with a (parametrized) rectangular obstacle. Numerical results show that the reduced basis approximation converges rapidly, the effectivities associated with the (inexpensive) rigorous a posteriori error bounds remain good even for reasonably small values of the penalty parameter, and that the effects of the penalty parameter are relatively benign.

We consider learning algorithms induced by regularization methods in the regression setting. We show that previously obtained error bounds for these algorithms, using a priori choices of the regularization parameter, can be attained using a suitable a posteriori choice based on cross-validation. In particular, these results prove adaptation of the rate of convergence of the estimators to the minimax rate induced by the "effective dimension" of the problem. We also show universal consistency for this broad class of methods which includes regularized least-squares, truncated SVD, Landweber iteration and ν-method.

We consider a wide class of error bounds developed in the context of statistical learning theory which are expressed in terms of functionals of the regression function, for instance, its norm in a reproducing kernel Hilbert space or other functional space. These bounds are unstable in the sense that a small perturbation of the regression function can induce an arbitrary large increase of the relevant functional and make the error bound useless. Using a known result involving Fano inequality, we show how stability can be recovered.

A new generalization of the Ostrowski–Gruss inequality is introduced in three different cases for functions in L¹[a, b] and L^∞[a, b] spaces and its application is given for deriving error bounds of some quadrature rules.

I trace the main steps of the first fifty-five years of my career as an applied mathematician, pausing from time to time to describe problems that arose in asymptotics and numerical analysis and had far-reaching effects on this career.

Lecture delivered at Asymptotics and Applied Analysis, Conference in Honor of Frank W. J. Olver's 75th Birthday, January 10–14, 2000, San Diego State University, San Diego, California.

Editors' Note: Frank W. J. Olver died on April 23, 2013. The following text was typed by his son, Peter J. Olver, from handwritten notes found among his papers. At times the writing is unpolished, including incomplete sentences, but the editors have decided to leave it essentially the way it was written. However, for clarity, some abbreviations have been written out in full. A couple of handwritten words could not be deciphered, and a guess for what was intended is enclosed in brackets: […]. Endnotes have been made into footnotes within the body of the article. References were mostly not included in the handwritten text, but rather listed in order at the end. Citations to references have been included at the appropriate point in the text.

The aim of this paper is to derive new representations for the Hankel and Bessel functions, exploiting the reformulation of the method of steepest descents by Berry and Howls [Hyperasymptotics for integrals with saddles, Proc. R. Soc. Lond. A434 (1991) 657–675]. Using these representations, we obtain a number of properties of the large-order asymptotic expansions of the Hankel and Bessel functions due to Debye, including explicit and numerically computable error bounds, asymptotics for the late coefficients, exponentially improved asymptotic expansions, and the smooth transition of the Stokes discontinuities.

In this paper, we derive new representations for the incomplete gamma function, exploiting the reformulation of the method of steepest descents by C. J. Howls [Hyperasymptotics for integrals with finite endpoints, Proc. Roy. Soc. London Ser. A439 (1992) 373–396]. Using these representations, we obtain a number of properties of the asymptotic expansions of the incomplete gamma function with large arguments, including explicit and realistic error bounds, asymptotics for the late coefficients, exponentially improved asymptotic expansions, and the smooth transition of the Stokes discontinuities.

In this paper, the regression learning algorithm with vector-valued RKHS is studied. We motivate the need for extending learning theory of scalar-valued functions and analze the learning performance. In this setting, the output data are from a Hilbert space $Y$, the associated RKHS consists of functions with values lie in $Y$. By providing mathematical aspects of vector-valued integral operator $L_K$, the capacity independent error bounds and learning rates are derived by means of the integral operator technique.

We consider the coefficient-based least squares regularized regression learning algorithm for the strongly and uniformly mixing samples. We obtain the capacity independent error bounds of the algorithm by means of the integral operator techniques. A standard assumption in theoretical study of learning algorithms for regression is the uniform boundedness of output sample values. We abandon this boundedness assumption and carry out the error analysis with output sample values satisfying a generalized moment hypothesis.

In this paper, we study the performance of kernel-based regression learning with non-iid sampling. The non-iid samples are drawn from different probability distributions with the same conditional distribution. A more general marginal distribution assumption is proposed. Under this assumption, the consistency of the regularization kernel network (RKN) and the coefficient regularization kernel network (CRKN) are proved. Satisfactory capacity independently error bounds and learning rates are derived by the techniques of integral operator.

We study distributed learning with partial coefficients regularization scheme in a reproducing kernel Hilbert space (RKHS). The algorithm randomly partitions the sample set ${\{z_i\}}_{i=1}^N$ into $m$ disjoint sample subsets of equal size. In order to reduce the complexity of algorithms, we apply a partial coefficients regularization scheme to each sample subset to produce an output function, and average the individual output functions to get the final global estimator. The error bound in the $L^2$-metric is deduced and the asymptotic convergence for this distributed learning with partial coefficients regularization is proved by the integral operator technique. Satisfactory learning rates are then derived under a standard regularity condition on the regression function, which reveals an interesting phenomenon that when $m\le N^s$ and $s$ is small enough, this distributed learning has the same convergence rate with the algorithm processing the whole data in one single machine.

The aim of this paper is to construct and analyze a fitted mesh finite difference method (FMFDM) for a class of time-dependent singularly perturbed convection–diffusion–reaction problems with a turning point. While such problems have been widely studied in the case of boundary layers, little has been achieved for interior layer problems. In addition, most of works have considered the coefficient functions as the functions of space only. In this work, we study problems where the coefficient functions are dependent on both space and time variables, and their solutions exhibit an interior layer. We derive the solution bounds and their derivatives. Then we use the classical implicit Euler method to discretize the time variable with a constant step-size. This method consists of two upwind finite difference schemes defined on an appropriate non-uniform mesh of Shishkin type. This mesh is fine near the turning point and coarse elsewhere. We prove that the method is almost first-order uniformly convergent with respect to the perturbation parameter. To improve the accuracy of the proposed method, we apply Richardson extrapolation technique. Numerical simulations are provided to confirm the theoretical findings.

Explicit algebraic expressions are derived for the roots of a cubic equation having one real and two complex roots. As opposed to traditional methods for direct (that is, non-iterative) solution, evaluation of the expressions is unconditionally numerically stable. A floating-point error analysis of the computations is given, which shows that the computed roots have extremely small relative errors. The computations are proved to be backward stable, that is, the computed roots are exact for a closely neighbouring cubic equation. Applications and uncertainty propagation are also considered.

In this paper, a performance comparison of SC-CDMA and MC-CDMA systems in Rayleigh fading channels is presented in the asynchronous uplink. Both coded and uncoded systems are considered as the uncoded systems show the behavior of the different signal models, the coded systems provide a realistic scenario for comparison. MC-CDMA is used in the frequency spreading approach. Serial concatenated coding (SCC) of a convolutional, a Walsh-Hadamard and a repetition code is used for the comparison of the coded systems. Iterative decoding is applied.

The bit error probability for MC-CDMA and SC-CDMA is calculated for the uncoded systems and a union bound for the coded systems is given. Potentials to meliorate the occurring disadvantages of both system designs are presented and differences in multi-user environments are demonstrated.