A new row ordering strategy for frontal solvers

The frontal method is a variant of Gaussian elimination that has been widely used since the mid 1970s. In the innermost loop of the computation the method exploits dense linear algebra kernels, which are straightforward to vectorize and parallelize. This makes the method attractive for modern computer architectures. However, unless the matrix can be ordered so that the front is never very large, frontal methods can require many more floating‐point operations for factorization than other approaches. We are interested in matrices that have a highly asymmetric structure. We use the idea of a row graph of an unsymmetric matrix combined with a variant of Sloan's profile reduction algorithm to reorder the rows. We also look at applying the spectral method to the row graph. Numerical experiments performed on a range of practical problems illustrate that our proposed MSRO and hybrid MSRO row ordering algorithms yield substantial reductions in the front sizes and, when used with a frontal solver, significantly enhance its performance both in terms of the factorization time and storage requirements. Copyright © 1999 John Wiley & Sons, Ltd.     

Weighted graph based ordering techniques for preconditioned conjugate gradient methods

We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.This work was supported by by the Natural Sciences and Engineering Research Council of Canada, and by the Information Technology Research Center, which is funded by the Province of Ontario.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices

The use of matchings is a powerful technique for scaling and ordering sparse matrices prior to the solution of a linear system Ax = b. Traditional methods such as implemented by the HSL software package MC64 use the Hungarian algorithm to solve the maximum weight maximum cardinality matching problem. However, with advances in the algorithms and hardware used by direct methods for the parallelization of the factorization and solve phases, the serial Hungarian algorithm can represent an unacceptably large proportion of the total solution time for such solvers. Recently, auction algorithms and approximation algorithms have been suggested as alternatives for achieving near‐optimal solutions for the maximum weight maximum cardinality matching problem. In this paper, the efficacy of auction and approximation algorithms as replacements for the Hungarian algorithm is assessed in the context of sparse symmetric direct solvers when used in problems arising from a range of practical applications. High‐cardinality suboptimal matchings are shown to be as effective as optimal matchings for the purposes of scaling. However, matching‐based ordering techniques require that matchings are much closer to optimality before they become effective. The auction algorithm is demonstrated to be capable of finding such matchings significantly faster than the Hungarian algorithm, but our ‐approximation matching approach fails to consistently achieve a sufficient cardinality. Copyright © 2015 The Authors Numerical Linear Algebra with Applications Published by John Wiley & Sons Ltd.     

The level probabilities for a simple loop ordering

Bartholomew's statistics for testing homogeneity of normal means with ordered alternatives have null distributions which are mixtures of chisquared or beta distributions depending on whether the variances are known or not. The mixing coefficients depend on the sample sizes and the order restriction. If a researcher knows which mean is smallest and which is largest, but does not know how the other means are ordered, then a loop ordering is appropriate. Exact expressions for the mixing coefficients for a loop ordering and arbitrary sample sizes are given for five or fewer populations and approximations are developed for more than five populations. Also, the mixing coefficients for a loop ordering with equal sample sizes are computed. These mixing coefficients also arise in testing the ordering as the null hypothesis, in testing order restrictions in exponential families and in testing order restrictions nonparametrically.This research was supported by the National Institutes of Health under Grant 1 R01 GM42584-01A1     

Vector complementarity problems with a variable ordering relation

In this paper, we investigate vector complementarity problems with a variable ordering relation. We establish existence results of a solution of a vector complementarity problem under an inclusive type condition. We obtain equivalence results among a vector complementarity problem, a vector variational inequality problem and other related problems.     

Analysis of iterative methods for saddle point problems: a unified approach

In this paper two classes of iterative methods for saddle point problems are considered: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. In both cases the iteration matrix can be transformed to a symmetric matrix by block diagonal matrices, a simple but essential observation which allows one to estimate the convergence rate of both classes by studying associated eigenvalue problems. The obtained estimates apply for a wider range of situations and are partially sharper than the known estimates in literature. A few numerical tests are given which confirm the sharpness of the estimates.

     

A new approach to energy-based sparse finite-element spaces

^{We show that the logarithmic factor in the standard error estimatefor sparse finite element (FE) spaces in arbitrary dimensiond is removable in the energy (H1) norm. Via a penalized sparsegrid condition, we then propose and analyse a new version ofthe energy-based sparse FE spaces introduced first in Bungartz(1992, Dünne Gitter und deren Anwendung bei der adaptivenLösung der dreidimensionalen Poisson-Gleichung. Dissertation.Munich, Germany: TU München) and known to satisfy an optimalapproximation property in the energy norm.}     

Invariant ordering on the simply connected covering of the Shilov boundary of a symmetric domain

The Shilov boundary of a symmetric domain D = G/K of tube type has the form G/P, where P is a maximal parabolic subgroup of the group G. We prove that the simply connected covering of the Shilov boundary possesses a unique (up to inversion) invariant ordering, which is induced by the continuous invariant ordering on the simply connected covering of G and can readily be described in terms of the corresponding Jordan algebra.     

Complex behavior in condensed matter: Morphological ordering in dissipative carrier systems

This article studies the dissipative thermodynamic regime of an electron system in bulk matter under the action of an external source of energy, which generates electron-hole pairs with a nonequilibrium distribution in energy space. It is shown that with increasing values of the source power (furthering the distance from equilibrium), and strictly in the case of a p-doped material, the carrier system displays complex behavior characterized by undergoing a succession of transitions between synergetically self-organized dissipative structures. The sequence goes from the homogeneous steady state (or stochastic thermal chaos), to sinusoidal spatial deviations (morphological ordering), to intricate ordered states (subharmonic bifurcations), to deterministic turbulent-like chaos (large amount of nonlinear periodic spatial organization of the Landau-Prigogine's type). The phenomenon may arise, for example, in semiconductor systems, molecular polymers, and protein molecular chains in biosystems. © 1997 John Wiley & Sons, Inc.     

A partially observable decision problem under a shifted likelihood ratio ordering

In this paper, we discuss a partially observable sequential decision problem under a shifted likelihood ratio ordering. Since we employ the Bayes' theorem for the learning procedure, we treat this problem under several assumptions. Under these assumptions, we obtain some fundamental results about the relation between prior and posterior information. We also consider an optimal stopping problem for this partially observable Markov decision process.     

Static super-replicating strategies for a class of exotic options

In this paper, we investigate static super-replicating strategies for European-type call options written on a weighted sum of asset prices. This class of exotic options includes Asian options and basket options among others. We assume that there exists a market where the plain vanilla options on the different assets are traded and hence their prices can be observed in the market. Both the infinite market case (where prices of the plain vanilla options are available for all strikes) and the finite market case (where only a finite number of plain vanilla option prices are observed) are considered. We prove that the finite market case converges to the infinite market case when the number of observed plain vanilla option prices tends to infinity.We show how to construct a portfolio consisting of the plain vanilla options on the different assets, whose pay-off super-replicates the pay-off of the exotic option. As a consequence, the price of the super-replicating portfolio is an upper bound for the price of the exotic option. The super-hedging strategy is model-free in the sense that it is expressed in terms of the observed option prices on the individual assets, which can be e.g. dividend paying stocks with no explicit dividend process known. This paper is a generalization of the work of Simon et al. [Simon, S., Goovaerts, M., Dhaene, J., 2000. An easy computable upper bound for the price of an arithmetic Asian option. Insurance Math. Econom. 26 (2–3), 175–184] who considered this problem for Asian options in the infinite market case. Laurence and Wang [Laurence, P., Wang, T.H., 2004. What’s a basket worth? Risk Mag. 17, 73–77] and Hobson et al. [Hobson, D., Laurence, P., Wang, T.H., 2005. Static-arbitrage upper bounds for the prices of basket options. Quant. Fin. 5 (4), 329–342] considered this problem for basket options, in the infinite as well as in the finite market case.As opposed to Hobson et al. [Hobson, D., Laurence, P., Wang, T.H., 2005. Static-arbitrage upper bounds for the prices of basket options. Quant. Fin. 5 (4), 329–342] who use Lagrange optimization techniques, the proofs in this paper are based on the theory of integral stochastic orders and on the theory of comonotonic risks.     

The linear ordering problem: Instances,search space analysis and algorithms

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.     

A new linear ordering of fuzzy numbers on subsets of {{\mathcal F}({\pmb{\mathbb{R}}}})

We introduce a novel linear order on every family of fuzzy numbers which satisfies the assumption that their modal values must be all different and must form a compact subset of . A distinct new feature is that our linear determined procedure employs the corresponding order of a class interval associated with a confidence measure which seems intuitively anticipated. It is worthy noting that although we start from an entirely different rationale, we introduce a fuzzy ordering which initially coincides with the one established earlier by Ramik and Rimanek. However, this fuzzy ordering does not apply when the supports of the fuzzy numbers overlap. In order to cover such cases we extent this initial fuzzy ordering to the “extended fuzzy order” (XFO). This new XFO method includes a possibility and a necessity measure which are compared with the widely accepted PD and NSD indices of D. Dubois and H. Prade. The comparison shows that our possibility and necessity measures comply better with our intuition.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

Loans,ordering and shortage costs in start-ups: a dynamic stochastic decision approach

Start-up companies are a vital ingredient in the success of a globalised networked world economy. We believe that such companies are interested in maximising the chance of surviving in the long term. We present a Markov decision model to analyse survival probabilities of start-up manufacturing companies. Our model examines the implications of their operating decisions, in particular how their inventory strategy is influenced by purchasing, shortage, transportation and ordering costs, as well as loans to the firm. It is shown that although the start-up company should be more conservative in its component purchasing strategy than if it were a well-established company it should not be too conservative. Nor is its strategy monotone in the amount of capital available.     

Simulated annealing: Use of a new tool in bin packing

Simulated annealing (statistical cooling) is applied to bin packing problems. Different cooling strategies are compared empirically and for a particular 100 item problem a solution is given which is most likely the best known so far.The work was partially done during the author's visit to the University of California, Berkeley, sponsored by the Humboldt-Foundation.     

Piecewise lexicographic programming: A new model for practical decision problems

A new model for practical decision problems is presented. It allows one to consider lexicographic preference structures by introducing the new class of piecewise lexicographic functions which impose a total order in the objective-and-constraint space. In this way, the concepts of objective and constraints are merged into a new unified notion of co-objective. Moreover, the lexicographic preference structure may be applied not only among different coobjectives, but also among different ranges of the same decision variable. The main merits of this model appear to be its versatility (it is able to deal with different types of multiobjective optimization situations without requiring user interaction) and its compactness (it does not require one to increase the original number of decision variables and constraints). A linear version of the model is investigated in more detail.