Some variant of Newton’s method with third-order convergence

We present a new modification of the Newton’s method which produces iterative methods with order of convergence three. A general error analysis providing the higher order of convergence is given, and the best efficiency, in term of function evaluations, of two of this new methods is provided.     

Sensitivity analysis for product design selection with an implicit value function

In product design selection the decision maker (DM) often does not have enough information about the end users’ needs to state the “preferences” with precision, as is required by many of the existing selection methods. We present, for the case where the DM gives estimates of the preferences, a concept for calculating a “robustness index.” The concept can be used with any iterative selection method that chooses a trial design for each iteration, and uses the DM’s preference parameters at that trial design to eliminate some design options which have lower value than the trial design. Such methods, like our previously published method, are applicable to cases where the DM’s value function is implicit. Our robustness index is a metric of the allowed variation between the actual and estimated preferences for which the set of non-eliminated trial designs (which could be singleton) will not change. The DM, through experience, can use the robustness index and other information generated in calculating the index to determine what action to take: make a final selection from the present set of non-eliminated designs; improve the precision of the preference estimates; or otherwise cope with the imprecision. We present an algorithm for finding the robustness index, and demonstrate and verify the algorithm with an engineering example and a numerical example.     

Universal Graphs with Forbidden Subgraphs and Algebraic Closure

We apply model theoretic methods to the problem of existence of countable universal graphs with finitely many forbidden connected subgraphs. We show that to a large extent the question reduces to one of local finiteness of an associated “algebraic closure” operator. The main applications are new examples of universal graphs with forbidden subgraphs and simplified treatments of some previously known cases.     

Trefftz,collocation, and other boundary methods—A comparison

In this article we survey the Trefftz method (TM), the collocation method (CM), and the collocation Trefftz method (CTM). We also review the coupling techniques for the interzonal conditions, which include the indirect Trefftz method, the original Trefftz method, the penalty plus hybrid Trefftz method, and the direct Trefftz method. Other boundary methods are also briefly described. Key issues in these algorithms, including the error analysis, are addressed. New numerical results are reported. Comparisons among TMs and other numerical methods are made. It is concluded that the CTM is the simplest algorithm and provides the most accurate solution with the best numerical stability. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules

Queue-mergesort is introduced by Golin and Sedgewick as an optimal variant of mergesorts in the worst case. In this paper, we present a complete analysis of the cost distribution of queue-mergesort, including the best, average, and variance cases. The asymptotic normality of its cost is also established under the uniform permutation model. We address the corresponding optimality problems and we show that if we fix the merging scheme then the optimal mergesort as far as the average number of comparisons is concerned is to divide as evenly as possible at each recursive stage (top-down mergesort). On the other hand, the variance of queue-mergesort reaches asymptotically the minimum value. We also characterize a class of mergesorts with the latter property. A comparative discussion is given on the probabilistic behaviors of top-down mergesort, bottom-up mergesort, and queue-mergesort. We derive an “invariance principle” for asymptotic linearity of divide-and-conquer recurrences based on general “power-of-2” rules of which the underlying dividing rule of queue-mergesort is a special case. These analyses reveal an interesting algorithmic feature for general power-of-2 rules.     

A comparison of procedures for estimating the parent probability distribution from a given set of fractiles

On one hand, eliciting subjective probabilities (fractiles) is a well-established procedure. On the other hand, knowledge of a subjective variable's central moments or distribution function is often assumed. However, the problem of converting elicited fractiles into the required moments or distribution function has been largely ignored. We show that this conversion problem is far from trivial, and that the most commonly used conversion procedures often produce huge errors. Alternative procedures are proposed; the “Tocher's curve” and “linear function of fractiles” methods are shown to be much more accurate than the commonly used procedures.     

Numerical comparison of nonlinear subgridscale models via adaptive mesh refinement

In this paper, we provide a method of evaluating the efficacy of nonlinear subgridscale models for use in the large eddy simulation of incompressible viscous flow problems. We compare subgridscale “artificial” viscosity models using a posteriori error estimation and adaptive mesh refinement. Specifically, we compare α-Laplacian based subgridscale models and discuss the benefits and limitations of different values of α for some standard benchmark problems for the Navier–Stokes equations.     

Counting and enumerating aggregate classifiers

We propose a generic model for the “weighted voting” aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to enumerate the number of distinct aggregate classifiers that arise in this model. When there are only two classes in the classification problem, we show that a class of functions that arises from aggregate classifiers coincides with the class of self-dual positive threshold Boolean functions.     

Negation of binomial coefficients

We extend the concept of a binomial coefficient to all integer values of its parameters. Our approach is purely algebraic, but we show that it is equivalent to the evaluation of binomial coefficients by means of the Γ-function. In particular, we prove that the traditional rule of “negation” is wrong and should be substituted by a slightly more complex rule. We also show that the “cross product” rule remains valid for the extended definition.     

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”     

k-Best Solutions under Distance Constraints in Valuated -Matroids

In discrete maximization problems one usually wants to find an optimal solution. However, in several topics like “alignments,” “automatic speech recognition,” and “computer chess” people are interested to find thekbest solutions for somek ≥ 2. We demand that theksolutions obey certain distance constraints to avoid that thekalternatives are too similar. Several results for valuated -matroids are presented, some of them concerning time complexity of algorithms.     

Representing probability measures using probabilistic processes

In the Type-2 Theory of Effectivity, one considers representations of topological spaces in which infinite words are used as “names” for the elements they represent. Given such a representation, we show that probabilistic processes on infinite words, under which each successive symbol is determined by a finite probabilistic choice, generate Borel probability measures on the represented space. Conversely, for several well-behaved types of space, every Borel probability measure is represented by a corresponding probabilistic process. Accordingly, we consider probabilistic processes as providing “probabilistic names” for Borel probability measures. We show that integration is computable with respect to the induced representation of measures.     

Newton's solution to the equiangular spiral problem and a new solution using only the equiangular property

This paper is a study of Proposition IX of Book I of Newton's Principia, the problem of determining the centripetal force for an equiangular spiral. In Newton's main proof of this proposition there is an error concerning his reason for the figure SPRQT being “given in kind,” and a very interesting technique of varying things in the neighborhood of a limit. This main proof utilized Newton's formula for the limit of SP²QT²/QR given in Corollary I to Proposition VI of the Principia. Newton also gave an alternate proof which utilized his formula for SY²PV given in Corollary III to Proposition VI. The “given” of Proposition IX was “a spiral PQS, cutting all the radii SP, SQ, &c., in a given angle.” Both the main proof and the alternate proof implicitly depend on the property of the equiangular spiral that the radius of curvature at any point is proportional to the pole distance SP. We here offer a new proof of Newton's proposition which does not depend on this implicit assumption.     

Formal and precise derivation of the Green functions for a simple potential

In formal scattering theory, the Green functions are obtained as solutions of a distributional equation. In this paper, we use the Sturm–Liouville theory to compute the Green functions within a rigorous mathematical theory. We shall show that both the Sturm–Liouville theory and the formal treatment yield the same Green functions. We shall also show how the analyticity of the Green functions as functions of the energy keeps track of the so-called “incoming” and “outgoing” boundary conditions.     

Bier Spheres and Posets

In 1992 Thomas Bier presented a strikingly simple method to produce a huge number of simplicial (n – 2)-spheres on 2n vertices, as deleted joins of a simplicial complex on n vertices with its combinatorial Alexander dual. Here we interpret his construction as giving the poset of all the intervals in a boolean algebra that “cut across an ideal.” Thus we arrive at a substantial generalization of Bier’s construction: the Bier posets Bier(P, I) of an arbitrary bounded poset P of finite length. In the case of face posets of PL spheres this yields cellular “generalized Bier spheres.” In the case of Eulerian or Cohen–Macaulay posets P we show that the Bier posets Bier(P, I) inherit these properties. In the boolean case originally considered by Bier, we show that all the spheres produced by his construction are shellable, which yields “many shellable spheres,” most of which lack convex realization. Finally, we present simple explicit formulas for the g-vectors of these simplicial spheres and verify that they satisfy a strong form of the g-conjecture for spheres.     

Construction algorithms for polynomial lattice rules for multivariate integration

We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.

     

Near-circularity of the error curve in complex Chebyshev approximation

Let f(z) be analytic on the unit disk, and let p^*(z) be the best (Chebyshev) polynomial approximation to f(z) on the disk of degree at most n. It is observed that in typical problems the “error curve,” the image of the unit circle under (f − p^*)(z), often approximates to a startling degree a perfect circle with winding number n + 1. This phenomenon is approached by consideration of related problems whose error curves are exactly circular, making use of a classical theorem of Carathéodory and Fejér. This leads to a technique for calculating approximations in one step that are roughly as close to best as the best approximation error curve is close to circular, and hence to strong theorems on near-circularity as the radius of the domain shrinks to 0 or as n increases to ∞. As a computational example, very tight bounds are given for approximation of e^z on the unit disk. The generality of the near-circularity phenomenon (more general domains, rational approximation) is discussed.     

On the Average Distribution of Inversive Pseudorandom Numbers

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. The authors have recently introduced a new method for obtaining nontrivial upper bounds on the multidimensional discrepancy of inversive congruential pseudorandom numbers in parts of the period. This method has also been used to study the multidimensional distribution of several other similar families of pseudorandom numbers. Here we apply this method to show that, “on average” over all initial values, much stronger results than those known for “individual” sequences can be obtained.     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

The difference in a problem of rations from the Rhind mathematical papyrus

In an ancient Egyptian problem of bread distribution from the Rhind mathematical papyrus (dated between 1794 and 1550 B.C.), a procedure of “false position” is used in the calculation of a series of five rations. The algorithm is only partially illustrated in the problem text, and last century's prevailing interpretations suggested a determination of the series by trial and error. The missing part of the computational procedure is reconstructed in this article as an application of the algorithm, exemplified in the preceding section of the papyrus, to calculate an unknown quantity by means of the method of “false position.”