ARMS: an algebraic recursive multilevel solver for general sparse linear systems

This paper presents a general preconditioning method based on a multilevel partial elimination approach. The basic step in constructing the preconditioner is to separate the initial points into two parts. The first part consists of ‘block’ independent sets, or ‘aggregates’. Unknowns of two different aggregates have no coupling between them, but those in the same aggregate may be coupled. The nodes not in the first part constitute what might be called the ‘coarse’ set. It is natural to call the nodes in the first part ‘fine’ nodes. The idea of the methods is to form the Schur complement related to the coarse set. This leads to a natural block LU factorization which can be used as a preconditioner for the system. This system is then solved recursively using as preconditioner the factorization that could be obtained from the next level. Iterations between levels are allowed. One interesting aspect of the method is that it provides a common framework for many other techniques. Numerical experiments are reported which indicate that the method can be fairly robust. Copyright © 2002 John Wiley & Sons, Ltd.     

Good equidistant codes constructed from certain combinatorial designs

An (n,M,d;q) code is called equidistant code if the Hamming distance between any two codewords is d. It was proved that for any equidistant (n,M,d;q) code, d?nM(q-1)/(M-1)q(=d_opt, say). A necessary condition for the existence of an optimal equidistant code is that d_opt be an integer. If d_opt is not an integer, i.e. the equidistant code is not optimal, then the code with d=⌊d_opt⌋ is called good equidistant code, which is obviously the best possible one among equidistant codes with parameters n,M and q. In this paper, some constructions of good equidistant codes from balanced arrays and nested BIB designs are described.     

Second-order cover inequalities

We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one.      

DNA profiling of shahtoosh

The population of the Tibetan Antelope (Pantholops hodgsonii) has recently declined dramatically due to the illegal trade in its wool. The animal lives at high altitude and is protected from the extremely cold climate due to a coat of very fine wool. These hairs are highly sought for weaving a shawl called shahtoosh. The large-scale poaching of the antelope has resulted in the species being placed on CITES Appendix I. We report on a method of DNA profiling on a confiscated shahtoosh using the cytochrome b (cyt b) gene to produce a test that will identify unambiguously the presence of P. hodgsonii. Two shahtoosh samples were provided by the Council of Agriculture, Taiwan, and ten shawl samples of sheep wool (Ovis aries), cashmere from the Kashmir goat (Capra hircus), and pashmina from the Himalayan goat (C. hircus) were collected from local stores for comparison. Two primer pairs were used to amplify a 271 bp fragment of cyt b gene which would distinguish these three species. The resulting amplification products were directly sequenced. When the DNA sequences were compared with the sequences registered in GenBank and EMBL databases, the sequences with the highest homology were the cyt b genes of P. hodgsonii, C. hircus, and O. aries. This study demonstrates that there is still sufficient DNA present in the finished wool of a shahtoosh shawl to allow DNA typing and the method established was highly plausible to identify the CITES protected species.     

Nested partitions for the large-scale extended job shop scheduling problem

This paper addresses the large-scale extended job shop scheduling problem while considering the bill of material and the working shifts constraints. We propose two approaches for the problem. One is based on dispatching rules (DR), and the other is an application of the Nested Partitions (NP) Framework. A sampling approach for the exact feasible subregion is developed to complete the NP method. Furthermore, to efficiently search each subregion, a weighted sampling approach is also presented. Computational experiments show that the NP method with weighted sampling can find good solutions for most large-scale extended job shop scheduling problems.     

Nested Cartesian grid method in incompressible viscous fluid flow

In this work, the local grid refinement procedure is focused by using a nested Cartesian grid formulation. The method is developed for simulating unsteady viscous incompressible flows with complex immersed boundaries. A finite-volume formulation based on globally second-order accurate central-difference schemes is adopted here in conjunction with a two-step fractional-step procedure. The key aspects that needed to be considered in developing such a nested grid solver are proper imposition of interface conditions on the nested-block boundaries, and accurate discretization of the governing equations in cells that are with block-interface as a control-surface. The interpolation procedure adopted in the study allows systematic development of a discretization scheme that preserves global second-order spatial accuracy of the underlying solver, and as a result high efficiency/accuracy nested grid discretization method is developed. Herein the proposed nested grid method has been widely tested through effective simulation of four different classes of unsteady incompressible viscous flows, thereby demonstrating its performance in the solution of various complex flow–structure interactions. The numerical examples include a lid-driven cavity flow and Pearson vortex problems, flow past a circular cylinder symmetrically installed in a channel, flow past an elliptic cylinder at an angle of attack, and flow past two tandem circular cylinders of unequal diameters. For the numerical simulations of flows past bluff bodies an immersed boundary (IB) method has been implemented in which the solid object is represented by a distributed body force in the Navier–Stokes equations. The main advantages of the implemented immersed boundary method are that the simulations could be performed on a regular Cartesian grid and applied to multiple nested-block (Cartesian) structured grids without any difficulty. Through the numerical experiments the strength of the solver in effectively/accurately simulating various complex flows past different forms of immersed boundaries is extensively demonstrated, in which the nested Cartesian grid method was suitably combined together with the fractional-step algorithm to speed up the solution procedure.     

Controlled multi-wave mixing via interacting dark states in a five-level system

We theoretically investigate the controlled multi-wave mixing (MWM) via interacting multi-dark states in a five-level system. Four-wave mixing (FWM) with three kinds of dual-dressed schemes (nested, sequential, and parallel schemes), six-wave mixing (SWM) with the quadruply nested dressed, and eight-wave mixing (EWM) with the parallel combination of two nested dressed schemes coexisting synchronously in a multi-dressed electromagnetically induced transparency system were well described. Through investigating their spectra, we found that these multi-dressed-states induced by various dressed schemes show strong interaction and interchange. Investigations of these multi-dressing schemes and interactions are very useful for understanding and controlling the generated high-order nonlinear optical signals.     

A FAST SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING

Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.     

F基数的表示与比较

本文给出了Ｆｕｚｚｙ映射的点式刻划,基于这种刻划,研究了Ｆｕｚｚ６ｙ基数的表示与比较。     

Continued radicals

If a ₁,a ₂,…,a _n are nonnegative real numbers and , then f ₁○f ₂○⋅⋅⋅○f _n (0) is a nested radical with terms a ₁,…,a _n . If it exists, the limit as n→∞ of such an expression is a continued radical. We consider the set of real numbers S(M) representable as a continued radical whose terms a ₁,a ₂,… are all from a finite set M. We give conditions on the set M for S(M) to be (a) an interval, and (b) homeomorphic to the Cantor set.