On the choice of a multiplication algorithm for polynomials and polynomial matrices

We investigate multiplication algorithms for dense and sparse polynomials and polynomial matrices over different numerical domains and obtain expressions for the complexity of multiplication of polynomials and polynomial matrices understood as the expectation of the number of arithmetic operations. These expressions for a set of parameters of practical interest are tabulated. The results of experiments with the corresponding programs are presented. Bibliography: 8 titles.     

Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications

This paper is concerned with accurate matrix multiplication in floating-point arithmetic. Recently, an accurate summation algorithm was developed by Rump et al. (SIAM J Sci Comput 31(1):189–224, 2008). The key technique of their method is a fast error-free splitting of floating-point numbers. Using this technique, we first develop an error-free transformation of a product of two floating-point matrices into a sum of floating-point matrices. Next, we partially apply this error-free transformation and develop an algorithm which aims to output an accurate approximation of the matrix product. In addition, an a priori error estimate is given. It is a characteristic of the proposed method that in terms of computation as well as in terms of memory consumption, the dominant part of our algorithm is constituted by ordinary floating-point matrix multiplications. The routine for matrix multiplication is highly optimized using BLAS, so that our algorithms show a good computational performance. Although our algorithms require a significant amount of working memory, they are significantly faster than ‘gemmx’ in XBLAS when all sizes of matrices are large enough to realize nearly peak performance of ‘gemm’. Numerical examples illustrate the efficiency of the proposed method.     

Asymptotic Optimality of Certain Multihypothesis Sequential Tests: Non‐i.i.d. Case

It is known that certain combinations of one‐sided sequential probability ratio tests are asymptotically optimal (relative to the expected sample size) for problems involving a finite number of possible distributions when probabilities of errors tend to zero and observations are independent and identically distributed according to one of the underlying distributions. The objective of this paper is to show that two specific constructions of sequential tests asymptotically minimize not only the expected time of observation but also any positive moment of the stopping time distribution under fairly general conditions for a finite number of simple hypotheses. This result appears to be true for general statistical models which include correlated and non‐homogeneous processes observed either in discrete or continuous time. For statistical problems with nuisance parameters, we consider invariant sequential tests and show that the same result is valid for this case. Finally, we apply general results to the solution of several particular problems such as a multi‐sample slippage problem for correlated Gaussian processes and for statistical models with nuisance parameters. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fast matrix multiplication is stable

We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of Bini and Lotti [Numer. Math. 36:63–72, 1980]. As a consequence of our analysis, we show that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms. We also show that new group-theoretic algorithms proposed in Cohn and Umans [Foundations of Computer Science, 44th Annual IEEE Symposium, pp. 438–449, 2003] and Cohn et al. [Foundations of Computer Science, 46th Annual IEEE Symposium, pp. 379–388, 2005] are all included in the class of algorithms to which our analysis applies, and are therefore numerically stable. We perform detailed error analysis for three specific fast group-theoretic algorithms. J. Demmel acknowledges support of NSF under grants CCF-0444486, ACI-00090127, CNS-0325873 and of DOE under grant DE-FC02-01ER25478. I. Dumitriu acknowledges support of the Miller Institute for Basic Research in Science. R. Kleinberg is supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship     

Numeration systems,fractals and stochastic processes

A numeration system Ω is a compactification of the set of real numbers keeping the actions of addition and positive multiplication in a natural way. That is, Ω is a compact metrizable space with #Ω≥2 to which ℝ acts additively andG acts multiplicatively satisfying the distributive law, whereG is a nontrivial closed multiplicative subgroup of ℝ₊. Moreover, the additive action is minimal and uniquely ergodic with 0-topological entropy, while the multiplication by λ has |log λ|-topological entropy attained uniquely by the unique invariant probability measure under the additive action. We construct Ω as above as a colored tiling space corresponding to a weighted substitution. This framework contains especially the substitution dynamical systems and β-transformation systems with periodic expansion of 1, both of which have discreteG. It also contains systems withG=ℝ₊. We study α-homogeneous cocycles on it with respect to the addition. They are interesting from the point of view of fractal functions or sets as well as self-similar processes. We obtain the zeta-functions of Ω with respect to the multiplication.     

Aging of spherical spin glasses

Sompolinski and Zippelius (1981) propose the study of dynamical systems whose invariant measures are the Gibbs measures for (hard to analyze) statistical physics models of interest. In the course of doing so, physicists often report of an “aging” phenomenon. For example, aging is expected to happen for the Sherrington-Kirkpatrick model, a disordered mean-field model with a very complex phase transition in equilibrium at low temperature. We shall study the Langevin dynamics for a simplified spherical version of this model. The induced rotational symmetry of the spherical model reduces the dynamics in question to an N-dimensional coupled system of Ornstein-Uhlenbeck processes whose random drift parameters are the eigenvalues of certain random matrices. We obtain the limiting dynamics for N approaching infinity and by analyzing its long time behavior, explain what is aging (mathematically speaking), what causes this phenomenon, and what is its relationship with the phase transition of the corresponding equilibrium invariant measures. Received: 8 July 1999 / Revised version: 2 June 2000 / Published online: 6 April 2001     

A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization

In recent years, there has been a growing interest for the experimental analysis in the field of evolutionary algorithms. It is noticeable due to the existence of numerous papers which analyze and propose different types of problems, such as the basis for experimental comparisons of algorithms, proposals of different methodologies in comparison or proposals of use of different statistical techniques in algorithms’ comparison. In this paper, we focus our study on the use of statistical techniques in the analysis of evolutionary algorithms’ behaviour over optimization problems. A study about the required conditions for statistical analysis of the results is presented by using some models of evolutionary algorithms for real-coding optimization. This study is conducted in two ways: single-problem analysis and multiple-problem analysis. The results obtained state that a parametric statistical analysis could not be appropriate specially when we deal with multiple-problem results. In multiple-problem analysis, we propose the use of non-parametric statistical tests given that they are less restrictive than parametric ones and they can be used over small size samples of results. As a case study, we analyze the published results for the algorithms presented in the CEC’2005 Special Session on Real Parameter Optimization by using non-parametric test procedures.     

Optimization of Randomized Monte Carlo Algorithms for Solving Problems with Random Parameters

Randomized Monte Carlo algorithms intended for statistical kernel estimation of the averaged solution to a problem with random baseline parameters are optimized. For this purpose, a criterion for the complexity of a functional Monte Carlo estimate is formulated. The algorithms involve a splitting method in which, for each realization of the parameters, a certain number of trajectories of the corresponding baseline process are constructed.     

Integer extended ABS algorithms and possible control of intermediate results for linear Diophantine systems

We present a new class of integer extended ABS algorithms for solving linear Diophantine systems. The proposed class contains the integer ABS (the so-called EMAS and our proposed MEMAS) algorithms and the generalized Rosser’s algorithm as its members. After an application of each member of the class a particular solution of the system and an integer basis for the null space of the coefficient matrix are at hand. We show that effective algorithms exist within this class by appropriately setting the parameters of the members of the new class to control the growth of intermediate results. Finally, we propose two effective heuristic rules for selecting certain parameters in the new class of integer extended ABS algorithms.      

Exact Asymptotics for the Distribution of the Time of Attaining the Maximum for a Trajectory of a Compound Poisson Process with Linear Drift

We consider the random process at − v+(pt) + v−(−qt), t ∈ (−∞, −), where v− and v+ are independent standard Poisson processes if t ≥ 0 and v−(t) = v+(t) = 0 if t < 0. Under certain conditions on the parameters a, p, and q, we study the distribution function G = G(x) of the time of attaining the maximum for a trajectory of this process. In the present article, we find an exact asymptotics for the tails of G. We also find a connection between this problem and the statistical problem of estimation of an unknown discontinuity point of a density function.     

On statistical manifolds of solutions of martingale problems

We consider geometrically regular statistical models defined by local densities of probability measures corresponding to discrete or continuous time Markov processes and smoothly depending on a finite dimensional parameter. Evolution equations are derived in terms of the generators of the underlying Markov additive processes for the elements of the related Fisher information matrix and the skewness tensor defining the Riemannian metric and the Amari-Chentsov's affine α-connections as functions of time and starting points of Markov processes. Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Published in Lietuvos Matematikes Rinkinys, Vol. 35, No. 4, pp. 456–468, October–December, 1995.     

模糊数的正向和反向表述及模糊数运算的拓展

模糊数运算的存在不可逆等问题,主要在于传统(正向)区间数严格限定所致.因此,提出了"反向区间数"的概念,利用该概念,能够给经典模糊分解定理、扩张原理新的表达形式.之后,分别以正(反)向区间为基础,分析模糊数的结构元表达形式,得到正(反)向区间对应结构元理论中单调增(减)函数.定义了反向区间数和反向区间数加、乘运算法则,利用结构元理论,证明了正、反向模糊数的加、乘运算解析表达式,得到了模糊方程解的判断定理.在保持传统运算法则不变的同时,对模糊数概念进行正(反)向的表述,并定义了二者的运算法则,这拓展了传统模糊数解的空间,进而解决模糊方程求解、不可逆等问题.通过算例看出,这两种表述在实际的计算过程中具有明显的意义.     

Development of effective algorithms for detecting breakdowns in models of systems

For a linear dynamic system with undetermined parameters we discuss the construction of algorithms and programs to exhibit breakdown criteria for breakdowns using Kalman filtering and sequential statistical analysis. Translated fromAlgoritmy Upravleniya i Identifikatsii, pp. 118–128, 1997.     

Algorithms for Minkowski products and implicitly‐defined complex sets

Minkowski geometric algebra is concerned with the complex sets populated by the sums and products of all pairs of complex numbers selected from given complex‐set operands. Whereas Minkowski sums (under vector addition in Rⁿ have been extensively studied, from both the theoretical and computational perspective, Minkowski products in R² (induced by the multiplication of complex numbers) have remained relatively unexplored. The complex logarithm reveals a close relation between Minkowski sums and products, thereby allowing algorithms for the latter to be derived through natural adaptations of those for the former. A novel concept, the logarithmic Gauss maps of plane curves, plays a key role in this process, furnishing geometrical insights that parallel those associated with the “ordinary” Gauss map. As a natural generalization of Minkowski sums and products, the computation of “implicitly‐defined” complex sets (populated by general functions of values drawn from given sets) is also considered. By interpreting them as one‐parameter families of curves, whose envelopes contain the set boundaries, algorithms for evaluating such sets are sketched. This revised version was published online in June 2006 with corrections to the Cover Date.     

Estimation of the mean in partially observed branching processes with general immigration

In the paper we investigate asymptotic properties of the branching process with non-stationary immigration which are sufficient for a natural estimator of the offspring mean based on partial observations to be strongly consistent and asymptotically normal. The estimator uses only a binomially distributed subset of the population of each generation. This approach allows us to obtain results without conditions on the criticality of the process which makes possible to develop a unified estimation procedure without knowledge of the range of the offspring mean. These results are to be contrasted with the existing literature related to i.i.d. immigration case where the asymptotic normality depends on the criticality of the process and are new for the fully observed processes as well. Examples of applications in the process with immigration with regularly varying mean and variance and subcritical processes with i.i.d. immigration are also considered.

     

Discrete optimization problems with interval parameters

Optimization problems on graphs with interval parameters are considered, and exponential and polynomial bounds for their computational complexity are obtained. For a certain subclass of polynomially solvable problems, two algorithms are proposed—one of them for finding an optimal solution and the other one for finding a suboptimal solution. Sufficient conditions for the statistical efficiency of the algorithm for finding a suboptimal solution are obtained.     

Asymptotic theory for estimating the parameters of a Lévy process

Summary We consider consistency and asymptotic normality of maximum likelihood estimators (MLE) for parameters of a Lévy process of the discontinuous type. The MLE are based on a single realization of the process on a given interval [0,t]. Depending on properties of the Lévy measure we either consider the MLE corresponding to jumps of size greater than ε and, keepingt fixed, we let ε tend to 0, or we consider the MLE corresponding to the complete information of the realization of the process on [0,t] and lett tend to ∞. The results of this paper improve in both generality and rigor previous asymptotic estimation results for such processes.     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

Perturbation analysis of theGI/GI/1 queue

We examine a family ofGI/GI/1 queueing processes generated by a parametric family of service time distributions,F(x,), and we show that under suitable conditions the corresponding customer stationary expectation of the system time is twice continuously differentiable with respect to. Expressions for the derivatives are given which are suitable for single run derivative estimation. These results are extended to parameters of the interarrival time distribution and expressions for the corresponding second derivatives (as well as partial second derivatives involving both interarrivai and service time parameters) are also obtained. Finally, we present perturbation analysis algorithms based on these expressions along with simulation results demonstrating their performance.     

A semidefinite framework for trust region subproblems with applications to large scale minimization

Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +α(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0<α(n)<1 is a fraction which decreases as the dimension increases. Research supported by the National Science and Engineering Research Council Canada.