A comparison of algorithms for the multivariate L 1-median

The L ₁-median is a robust estimator of multivariate location with good statistical properties. Several algorithms for computing the L ₁-median are available. Problem specific algorithms can be used, but also general optimization routines. The aim is to compare different algorithms with respect to their precision and runtime. This is possible because all considered algorithms have been implemented in a standardized manner in the open source environment R. In most situations, the algorithm based on the optimization routine NLM (non-linear minimization) clearly outperforms other approaches. Its low computation time makes applications for large and high-dimensional data feasible.     

基于Nie-Tan算法的区间二型模糊集质心计算:改变主变量采样个数

计算区间二型模糊集的质心(也称降型)是区间二型模糊逻辑系统中的一个重要模块。Karnik-Mendel(KM)迭代算法通常被认为是计算区间二型模糊集质心的标准算法。尽管如此,KM算法涉及复杂的计算过程,不利于实时应用。在各种改进类算法中,非迭代的Nie-Tan(NT)算法可节省计算消耗。此外,连续版本NT(CNT,continuous version of NT)算法被证明是计算质心的准确算法。本文比较了离散版本NT算法中求和运算和连续版本NT算法中求积分运算,通过四个计算机仿真例子证实了当适度增加区间二型模糊集主变量采样个数时,NT算法的计算结果可以精确地逼近CNT算法。     

Multivariate Frobenius–Padé approximants: Properties and algorithms

The aim of this paper is to construct rational approximants for multivariate functions given by their expansion in an orthogonal polynomial system. This will be done by generalizing the concept of multivariate Padé approximation. After defining the multivariate Frobenius–Padé approximants, we will be interested in the two following problems: the first one is to develop recursive algorithms for the computation of the value of a sequence of approximants at a given point. The second one is to compute the coefficients of the numerator and denominator of the approximants by solving a linear system. For some particular cases we will obtain a displacement rank structure for the matrix of the system we have to solve. The case of a Tchebyshev expansion is considered in more detail.     

Computation of general correlation coefficients for interval data

This paper provides a comprehensive analysis of computational problems concerning calculation of general correlation coefficients for interval data. Exact algorithms solving this task have unacceptable computational complexity for larger samples, therefore we concentrate on computational problems arising in approximate algorithms. General correlation coefficients for interval data are also given by intervals. We derive bounds on their lower and upper endpoints. Moreover, we propose a set of heuristic solutions and optimization methods for approximate computation. Extensive simulation experiments show that the heuristics yield very good solutions for strong dependencies. In other cases, global optimization using evolutionary algorithm performs best. A real data example of autocorrelation of cloud cover data confirms the applicability of the approach.     

Experiments with parallel algorithms for combinatorial problems

In the last decade many models for parallel computation have been proposed and many parallel algorithms have been developed. However, few of these models have been realized and most of these algorithms are supposed to run on idealized, unrealistic parallel machines.The parallel machines constructed so far all use a simple model of parallel computation. Therefore, not every existing parallel machine is equally well suited for each type of algorithm. The adaptation of a certain algorithm to a specific parallel architecture may severely increase the complexity of the algorithm or severely obscure its essence.Little is known about the performance of some standard combinatorial algorithms on existing parallel machines. In this paper we present computational results concerning the solution of knapsack, shortest paths and change-making problems by branch and bound, dynamic programming, and divide and conquer algorithms on the ICL-DAP (an SIMD computer), the Manchester dataflow machine and the CDC-CYBER-205 (a pipeline computer).     

Computation of bounds for eigenvalues of structures with interval parameters

In this paper, the computation of eigenvalue bounds for generalized interval eigenvalue problem is considered. Two algorithms based on the properties of continuous functions are developed for evaluating upper and lower eigenvalue bounds of structures with interval parameters. The method can provide the tightest bounds within a given precision. Numerical examples illustrate the effectiveness of the proposed method.     

Numerical Computation of Multivariate Normal Probabilities

Abstract

The numerical computation of a multivariate normal probability is often a difficult problem. This article describes a transformation that simplifies the problem and places it into a form that allows efficient calculation using standard numerical multiple integration algorithms. Test results are presented that compare implementations of two algorithms that use the transformation with currently available software.     

The exact likelihood for a multivariate ARMA model

A number of algorithms are presented for calculating the exact likelihood of a multivariate ARMA model. There are two aspects to the algorithms. Firstly, the parameterization is in terms of AR parameters and autocovariances. This obviates difficulties with initial MA estimates. Secondly, the algorithms explicitly account for specification of the lag structure of the multivariate time series. Additionally, an algorithm is presented to deal with missing data. The algorithms are, of themselves, not new but they have not been applied to likelihood construction in the manner discussed here.     

Numerically stable,scalable formulas for parallel and online computation of higher-order multivariate central moments with arbitrary weights

Formulas for incremental or parallel computation of second order central moments have long been known, and recent extensions of these formulas to univariate and multivariate moments of arbitrary order have been developed. Such formulas are of key importance in scenarios where incremental results are required and in parallel and distributed systems where communication costs are high. We survey these recent results, and improve them with arbitrary-order, numerically stable one-pass formulas which we further extend with weighted and compound variants. We also develop a generalized correction factor for standard two-pass algorithms that enables the maintenance of accuracy over nearly the full representable range of the input, avoiding the need for extended-precision arithmetic. We then empirically examine algorithm correctness for pairwise update formulas up to order four as well as condition number and relative error bounds for eight different central moment formulas, each up to degree six, to address the trade-offs between numerical accuracy and speed of the various algorithms. Finally, we demonstrate the use of the most elaborate among the above mentioned formulas, with the utilization of the compound moments for a practical large-scale scientific application.     

On the fast solution of Toeplitz-block linear systems arising in multivariate approximation theory

When constructing multivariate Padé approximants, highly structured linear systems arise in almost all existing definitions [10]. Until now little or no attention has been paid to fast algorithms for the computation of multivariate Padé approximants, with the exception of [17]. In this paper we show that a suitable arrangement of the unknowns and equations, for the multivariate definitions of Padé approximant under consideration, leads to a Toeplitz-block linear system with coefficient matrix of low displacement rank. Moreover, the matrix is very sparse, especially in higher dimensions. In Section 2 we discuss this for the so-called equation lattice definition and in Section 3 for the homogeneous definition of the multivariate Padé approximant. We do not discuss definitions based on multivariate generalizations of continued fractions [12, 25], or approaches that require some symbolic computations [6, 18]. In Section 4 we present an explicit formula for the factorization of the matrix that results from applying the displacement operator to the Toeplitz-block coefficient matrix. We then generalize the well-known fast Gaussian elimination procedure with partial pivoting developed in [14, 19], to deal with a rectangular block structure where the number and size of the blocks vary. We do not aim for a superfast solver because of the higher risk for instability. Instead we show how the developed technique can be combined with an easy interval arithmetic verification step. Numerical results illustrate the technique in Section 5.Research partly funded by FWO-Vlaanderen.     

Multivariate Padé approximants revisited

Several definitions of multivariate Padé approximants have been introduced during the last decade. We will here consider all types of definitions based on the choice that the coefficients in numerator and denominator of the multivariate Padé approximant are defined by means of a linear system of equations. In this case a determinant representation for the multivariate Padé approximant exists. We will show that a general recursive algorithm can be formulated to compute a multivariate Padé approximant given by any definition of this type. Here intermediate results in the recursive computation scheme will also be multivariate Padé approximants. Up to now such a recursive computation of multivariate Padé approximants only seemed possible in some special cases.     

New enclosure algorithms for the verified solutions of nonlinear Volterra integral equations

This paper is concerned with new algorithms which provide the sharp bounds that are guaranteed to contain the exact solutions of nonlinear Volterra integral equations. We develop new enclosure algorithms based on the interval methods which was first introduced by Moore in [24] together with the Taylor polynomials to improve the accuracy of the scheme by reducing the width of interval solutions. The modified methods calculate a priori bound automatically in parallel with the computation of solutions of integral equations. We will show that the accuracy of the proposed algorithms is dependent on the number of interval subdivisions. Some numerical experiments are also included to demonstrate the validity and applicability of the scheme and showing a marked improvement in comparison with the recent existing numerical results.     

Number-theoretic interpretation and construction of a digital circle

This paper presents a new interpretation of a digital circle in terms of the distribution of square numbers in discrete intervals. The number-theoretic analysis that leads to many important properties of a digital circle succinctly captures the original perspectives of digital calculus and digital geometry for its visualization and characterization. To demonstrate the capability and efficacy of the proposed method, two simple algorithms for the construction of digital circles, based on simple number-theoretic concepts, have been reported. Both the algorithms require only a few primitive operations and are completely devoid of any floating-point computation. To speed up the computation, especially for circular arcs of high radii, a hybridized version of these two algorithms has been given. Experimental results have been furnished to elucidate the analytical power and algorithmic efficiency of the proposed approach. It has been also shown, how and why, for sufficiently high radius, the number-theoretic technique can expedite a circle construction algorithm.     

Computing regularities in strings: A survey

The aim of this survey is to provide insight into the sequential algorithms that have been proposed to compute exact “regularities” in strings; that is, covers (or quasiperiods), seeds, repetitions, runs (or maximal periodicities), and repeats. After outlining and evaluating the algorithms that have been proposed for their computation, I suggest possibly productive future directions of research.     

Minimizing makespan for two parallel machines with job limit on each availability interval

We consider the problem of scheduling jobs on two parallel machines that are not continuously available for processing. The machine is not available after processing a fixed number of jobs in order to make precision adjustment of machines such as in wafer manufacturing, to reload the feeder in printed circuit board production, or to undertake any other maintenance works such as cleaning and safety inspections. The objective of the problem is to minimize the makespan. Two different scheduling horizons are investigated for this problem. For the short-term scheduling horizon, we consider only the time period before the unavailability interval, while for the long-term horizon, machines are allowed to restart processing after the unavailability interval. For both cases, which are strongly NP-hard, exact optimization algorithms based on the branch and bound method are proposed. Although the algorithms have exponential time complexities, computational results show that they can solve optimally the various-sized problems in reasonable computation time.     

Bandwidth of bipartite permutation graphs in polynomial time

We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs.     

Hybrid symbolic-numeric algorithms for computational convex analysis

Computational convex analysis focuses on developing efficient tools to compute fundamental transforms arising in convex analysis. Symbolic computation tools have been developed, and have allowed more insight into the calculation of the Fenchel conjugate and related transforms. When such tools are not applicable e.g. when there is no closed form, fast transform algorithms perform numerical computation efficiently. However, computing the composition of several transforms is difficult to achieve with fast transform algorithms, which is the case for the recently introduced proximal average operator. We consider the class of piecewise linear-quadratic functions which, being closed under the most relevant operations in convex analysis, allows the robust and efficient numerical computation of compositions of transforms like the proximal average. The algorithms presented are hybrid symbolic-numeric: they first compute a piecewise linear-quadratic approximation of the function, and then manipulate the approximation symbolically. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An architecture independent study of parallel segment trees

We study the computation, communication and synchronization requirements related to the construction and search of parallel segment trees in an architecture independent way. Our proposed parallel algorithms are optimal in space and time compared to the corresponding sequential algorithms utilized to solve the introduced problems and are described in the context of the bulk-synchronous parallel (BSP) model of computation. Our methods are more scalable and can thus be made to work for larger values of processor size p relative to problem size n than other segment tree related algorithms that have been described on other realistic distributed-memory parallel models and also provide a natural way to approach searching problems on latency-tolerant models of computation that maintains a balanced query load among the processors.     

Efficient strategy for reliability-based optimization design of multidisciplinary coupled system with interval parameters

Non-probabilistic reliability based multidisciplinary design optimization has been widely acknowledged as an advanced methodology for complex system design when the data is insufficient. In this work, the uncertainty propagation analysis method in multidisciplinary system based on subinterval theory is firstly studied to obtain the uncertain responses. Then, based on the non-probabilistic set theory, the interval reliability based multidisciplinary design optimization model is established. Considering that the gradient information of interval reliability cannot be acquired in the whole design domain, which causes convergence difficulties and prohibitive computation, an interval reliability displacement based multidisciplinary design optimization method is proposed to address the issue. In the proposed method, the interval reliability displacement is introduced to measure the degree of interval reliability. By doing so, not only the connotation of the interval reliability is guaranteed, but more importantly, the partial gradient region for interval reliability is equivalently converted into full gradient region for reliability displacement. Consequently, the gradient information can be acquired under any circumstances and thus the convergence process is highly accelerated by utilizing the gradient optimization algorithms.