Bounds on degrees of p-adic separating polynomials

We study a discrete optimization problem introduced by Babai, Frankl, Kutin, and Štefankovi? (2001), which provides bounds on degrees of polynomials with p-adically controlled behavior. Such polynomials are of particular interest because they furnish bounds on the size of set systems satisfying Frankl-Wilson-type conditions modulo prime powers, with lower degree polynomials providing better bounds. We elucidate the asymptotic structure of solutions to the optimization problem, and we also provide an improved method for finding solutions in certain circumstances.     

Polynomial Acceleration Methods for Solving Singular Systems of Linear Equations

In this paper we study the polynomial acceleration methods for solving singular linear systems. We establish iterative schemes, show their convergence and find iteration error bounds.     

Stability of central finite difference schemes for the Heston PDE

This paper deals with stability in the numerical solution of the prominent Heston partial differential equation from mathematical finance. We study the well-known central second-order finite difference discretization, which leads to large semidiscrete systems with nonnormal matrices A. By employing the logarithmic spectral norm we prove practical, rigorous stability bounds. Our theoretical stability results are illustrated by ample numerical experiments. We also apply the analysis to obtain useful stability bounds for time discretization methods.     

Trigonometric spline and spectral bounds for the solution of linear time-periodic systems

Linear time-periodic systems arise whenever a nonlinear system is linearized about a periodic trajectory. Examples include anisotropic rotor-bearing systems and parametrically excited systems. The structure of the solution to linear time-periodic systems is known due to Floquet’s Theorem. We use this information to derive a new norm which yields two-sided bounds on the solution and in this norm vibrations of the solution are suppressed. The obtained results are a generalization for linear time-invariant systems. Since Floquet’s Theorem is non-constructive, the applicability of the aforementioned results suffers in general from an unknown Floquet normal form. Hence, we discuss trigonometric splines and spectral methods that are both equipped with rigorous bounds on the solution. The methodology differs systematically for the two methods. While in the first method the solution is approximated by trigonometric splines and the upper bound depends on the approximation quality, in the second method the linear time-periodic system is approximated and its solution is represented as an infinite series. Depending on the smoothness of the time-periodic system, we formulate two upper bounds which incorporate the approximation error of the linear time-periodic system and the truncation error of the series representation. Rigorous bounds on the solution are necessary whenever reliable results are needed, and hence they can support the analysis and, e.g., stability or robustness of the solution may be proven or falsified. The theoretical results are illustrated and compared to trigonometric spline bounds and spectral bounds by means of three examples that include an anisotropic rotor-bearing system and a parametrically excited Cantilever beam.     

Semilocal convergence of a family of iterative methods in Banach spaces

In this work, we prove a third and fourth convergence order result for a family of iterative methods for solving nonlinear systems in Banach spaces. We analyze the semilocal convergence by using recurrence relations, giving the existence and uniqueness theorem that establishes the R-order of the method and the priori error bounds. Finally, we apply the methods to two examples in order to illustrate the presented theory.     

Quantitative approximations of evolving probability measures and sequential Markov chain Monte Carlo methods

We study approximations of evolving probability measures by an interacting particle system. The particle system dynamics is a combination of independent Markov chain moves and importance sampling/resampling steps. Under global regularity conditions, we derive non-asymptotic error bounds for the particle system approximation. In a few simple examples, including high dimensional product measures, bounds with explicit constants of feasible size are obtained. Our main motivation are applications to sequential MCMC methods for Monte Carlo integral estimation.     

Sub-stochastic matrix analysis for bounds computation—Theoretical results

Performance evaluation of complex systems is a critical issue and bounds computation provides confidence about service quality, reliability, etc. of such systems. The stochastic ordering theory has generated a lot of works on bounds computation. Maximal lower and minimal upper bounds of a Markov chain by a st-monotone one exist and can be efficiently computed. In the present work, we extend simultaneously this last result in two directions. On the one hand, we handle the case of a maximal monotone lower bound of a family of Markov chains where the coefficients are given by numerical intervals. On the other hand, these chains are sub-chains associated to sub-stochastic matrices. We prove the existence of this maximal bound and we provide polynomial time algorithms to compute it both for discrete and continuous Markov chains. Moreover, it appears that the bounding sub-chain of a family of strictly sub-stochastic ones is not necessarily strictly sub-stochastic. We establish a characterization of the families of sub-chains for which these bounds are strictly sub-stochastic. Finally, we show how to apply these results to a classical model of repairable system. A forthcoming paper will present detailed numerical results and comparison with other methods.     

Comparison of Two Sets of First-Order Conditions as Bases of Interior-Point Newton Methods for Optimization with Simple Bounds

In this paper, we compare the behavior of two Newton interior-point methods derived from two different first-order necessary conditions for the same nonlinear optimization problem with simple bounds. One set of conditions was proposed by Coleman and Li; the other is the standard KKT set of conditions. We discuss a perturbation of the CL conditions for problems with one-sided bounds and the difficulties involved in extending this to problems with general bounds. We study the numerical behavior of the Newton method applied to the systems of equations associated with the unperturbed and perturbed necessary conditions. Preliminary numerical results for convex quadratic objective functions indicate that, for this class of problems, the Newton method based on the perturbed KKT formulation appears to be the more robust.     

Existence of solutions to second-order BVPs on time scales

We consider a boundary value problem (BVP) for systems of second-order dynamic equations on time scales. Using methods involving dynamic inequalities, we formulate conditions under which all solutions to a certain family of systems of dynamic equations satisfy certain a priori bounds. These results are then applied to guarantee the existence of solutions to BVPs for systems of dynamic equations on time scales.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Mixed volume techniques for embeddings of Laman graphs

Determining the number of embeddings of Laman graph frameworks is an open problem which corresponds to understanding the solutions of the resulting systems of equations. In this paper we investigate the bounds which can be obtained from the viewpoint of Bernstein's Theorem. The focus of the paper is to provide methods to study the mixed volume of suitable systems of polynomial equations obtained from the edge length constraints. While in most cases the resulting bounds are weaker than the best known bounds on the number of embeddings, for some classes of graphs the bounds are tight.     

Attractors and Dimensions for Discretizations of a Generalized Ginzburg-Landau Equation

In this paper, we discretize the generalized Ginzburg-Landau equations with the periodic boundary condition by the finite difference method in spatial direction. It is proved that for each mesh size, there exist at tractors for the discretized systems. The bounds for the Hausdorff dimensions of the discrete attractors are obtained, and the various bounds are independtmt of tho mesh sizes.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

Block triangular preconditioners for linearization schemes of the Rayleigh–Bénard convection problem

In this paper, we compare two block triangular preconditioners for different linearizations of the Rayleigh–Bénard convection problem discretized with finite element methods. The two preconditioners differ in the nested or nonnested use of a certain approximation of the Schur complement associated to the Navier–Stokes block. First, bounds on the generalized eigenvalues are obtained for the preconditioned systems linearized with both Picard and Newton methods. Then, the performance of the proposed preconditioners is studied in terms of computational time. This investigation reveals some inconsistencies in the literature that are hereby discussed. We observe that the nonnested preconditioner works best both for the Picard and for the Newton cases. Therefore, we further investigate its performance by extending its application to a mixed Picard–Newton scheme. Numerical results of two‐ and three‐dimensional cases show that the convergence is robust with respect to the mesh size. We also give a characterization of the performance of the various preconditioned linearization schemes in terms of the Rayleigh number.     

Mean queue size in a queue with discrete autoregressive arrivals of order <Emphasis Type="Italic">p</Emphasis>

We consider a discrete time single server queueing system where the arrival process is governed by a discrete autoregressive process of order p (DAR(p)), and the service time of a customer is one slot. For this queueing system, we give an expression for the mean queue size, which yields upper and lower bounds for the mean queue size. Further we propose two approximation methods for the mean queue size. One is based on the matrix analytic method and the other is based on simulation. We show, by illustrations, that the proposed approximations are very accurate and computationally efficient.     

Reliability and expectation bounds for coherent systems with exchangeable components

Sharp upper and lower bounds are obtained for the reliability functions and the expectations of lifetimes of coherent systems based on dependent exchangeable absolutely continuous components with a given marginal distribution function, by use of the concept of Samaniego's signature. We first show that the distribution of any coherent system based on exchangeable components with absolutely continuous joint distribution is a convex combination of distributions of order statistics (equivalent to the k-out-of-n systems) with the weights identical with the values of the Samaniego signature of the system. This extends the Samaniego representation valid for the case of independent and identically distributed components. Combining the representation with optimal bounds on linear combinations of distribution functions of order statistics from dependent identically distributed samples, we derive the corresponding reliability and expectation bounds, dependent on the signature of the system and marginal distribution of dependent components. We also present the sequences of exchangeable absolutely continuous joint distributions of components which attain the bounds in limit. As an application, we obtain the reliability bounds for all the coherent systems with three and four exchangeable components, expressed in terms of the parent marginal reliability function and specify the respective expectation bounds for exchangeable exponential components, comparing them with the lifetime expectations of systems with independent and identically distributed exponential components.     

并行多分裂AOR迭代法的收敛定理

对解非奇异线性方程组的并行多分裂ＡＯＲ方法,本文给出了该方法的收敛性定理,同时也给出了该方法的迭代矩阵的谱半径的上界估计式。     

Tail bounds for the joint distribution of the surplus prior to and at ruin

For the classical risk model with Poisson arrivals, we study the (bivariate) tail of the joint distribution of the surplus prior to and at ruin. We obtain some exact expressions and new bounds for this tail, and we suggest three numerical methods that may yield upper and lower bounds for it. As a by-product of the analysis, we obtain new upper and lower bounds for the probability and severity of ruin. Many of the bounds in the present paper improve and generalise corresponding bounds that have appeared earlier. For the numerical bounds, their performance is also compared against bounds available in the literature.     

A GRASP heuristic for the manufacturing cell formation problem

In this work, we address the Manufacturing Cell Formation Problem (MCFP). Cellular Manufacturing is a production strategy that has emerged to reduce materials handling and set up times in order to reduce lead times in production systems and to improve customer??s service levels while reducing costs. We propose a GRASP heuristic to obtain lower bounds for the optimal solution of the problem. To evaluate the performance of the proposed method, we test the heuristic with different instances from the literature and compare the results obtained with those provided by other heuristic methods from the literature. According to the obtained results, the proposed GRASP procedure provides good quality lower bounds with reasonable computational effort.     

On the boundedness of rough oscillatory singular integrals on Triebel-Lizorkin spaces

We obtain appropriate sharp bounds on Triebel-Lizorkin spaces for rough oscillatory integrals with polynomial phase. By using these bounds and using an extrapolation argument we obtain some new and previously known results for oscillatory integrals under very weak size conditions on the kernel functions.