Experimental numerical studies on a supercomputer of natural convection in an enclosure with localized heating

We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by −G/r^p + H/r^q.

In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time t_k = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations F_i,k = m_ia_i,k, I = 1, 2, 3, …, n, where m_i is the mass of the ith particle.

Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others.     

Variational geometry: A new method for modifying part geometry for finite element analysis

Interactive graphic methods have the potential to significantly reduce the cost associated with pre- and post-processing of finite element analyses. One area of particular importance is the creation and modification of part geometry.

This paper describes a powerful method for modification of geometry for finite element analysis pre-processors. The method, called “Variational Geometry”, uses a single representation to describe the entire family of geometries that share a generic shape.

A solid geometric model of a component is defined with respect to a set of scalar parameters. Dimensions, such as those which appear on a mechanical drawing, are treated as constraints on the permissible values of these parameters. Constraints on the geometry are expressed as a set of non-linear algebraic equations. The values of the parameters and hence the geometry may be determined by solving the set of non-linear constraint equations.

A procedure for minimizing the computational requirements is presented. For a part with n degrees of freedom, the solution time is shown to be O(n).     

A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw.     

A new routing algorithm for multirate rearrangeable Clos networks

In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the “grouping algorithm”. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that m = 2n+(n−1)/2^k is a sufficient number of middle-stage switches for the symmetric three-stage Clos network C(n,m,r) to be multirate rearrangeable, where k is any positive integer and rn/(2^k−1).     

On the number of occurrences of all short factors in almost all words

We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k(n) over A as n→∞, provided limsup_n→∞ k(n)/log n<1/log m.

In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where lim_n→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0.     

Reaching a goal with directional uncertainty

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle centered around the specified direction.

First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region from where we can reach infinity with a directional uncertainty of . We prove that the maximum complexity of is O(n/⁵). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k³m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of . For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.     

Optimal bounds for the approximation of boolean functions and some applications

This paper presents an optimal bound on the Shannon function L(n,m,) that gives the worstcase circuit-size complexity to approximate, within an approximation degree at least , partial boolean functions having n inputs and domain size m. That is

Full-size image

. Our bound applies to any partial boolean function and any approximation degree, and thus completes the study of boolean function approximation introduced by Pippenger (1977).

Our results give an upper bound for the hardness function h(ƒ), introduced by Nisan and Wigderson (1994), which denotes the minimum value l for which there exists a circuit of size at most l that approximates a boolean function ƒ with degree at least 1/l. Indeed, if H(n) denotes the maximum hardness value achieved by boolean functions with n inputs, we prove that for almost every nH(n)n/3 + n² + O(1). The exponent n/3 in the above inequality implies that no family of boolean functions exists which has ‘full’ hardness. This fact establishes connections with Allender and Strauss' (1994) work that explores the structure of BPP.

Finally, we show that for almost every n and for almost every boolean function ƒ of n inputs we have h(ƒ)2^{n/3−2 log n}. The contribution in the proof of the upper bound for L(n, m, ) can be viewed as a set of technical results that globally show how boolean linear operators are ‘well’ distributed on the class of 4-regular domains. This property is then applied to approximate partial boolean functions on general domains using a suitable composition of boolean linear operators.     

An algorithmic view of gene teams

Comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. Many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are “not too far” in all genomes. In this paper, we propose a unifying concept, called gene teams, which can be adapted to various notions of distance. We present two algorithms for identifying gene teams formed by n genes placed on m linear chromosomes. The first one runs in O(mn log² n) and uses a divide and conquer approach based on the formal properties of gene teams. We next propose an optimization of the original algorithm, and, in order to better understand the complexity bound of the algorithms, we recast the problem in the Hopcroft's partition refinement framework. This allows us to analyze the complexity of the algorithms with elegant amortized techniques. Both algorithms require linear space. We also discuss extensions to circular chromosomes that achieve the same complexity.     

A new way of counting n

In this paper, we shall give a combinatorial proof of the following equation:

,

where m and n are positive integers, m ≤ n, and k₁, k₂, …, k_n-1 are nonnegative integers.     

A new complexity bound for the least-squares problem

For a least-squares problem of m degree polynomial regression with n measured values (n ≥ m + 1), the traditional methods need O(n²m) arithmetic operations. We prove that the arithmetic complexity of this problem does not exceed O(nlog²₂m).     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

A method of inexact steepest descent for systems of linear equations

Our approach combines the method of inexact steepest descent with the method of contractor directions to obtain an algorithm for solving systems of linear equations. In order to enhance the scope of applicability, we consider an iterative method with variable step-size iterations. We prove the convergence and given an error estimate for our method.

The algorithm is well-suited for parallel computation. In fact, for systems with m equations and n unknowns, each iteration may be computed in parallel time O(log m + log n), on an EREW PRAM with O(mn) processors.     

Subspace selection algorithms to be used with the nonlinear projection methods in solving systems of nonlinear equations

The nonlinear projection methods are minimization procedures for solving systems of nonlinear equations. They permit reevaluation of n_k, 1 ≤ n_k ≤ n, components of the approximate solution vector at each iteration step where n is the dimension of the system. At iteration step k, the reduction in the norm of the residue vector depends upon the n_k components which are reevaluated. These n_k components are obtained by solving a linear system.

We present two algorithms for determining the components to be modified at each iteration of the nonlinear projection method and compare the use of these algorithms to Newton's method. The computational examples demonstrate that Newton's method, which reevaluates all components of the approximate solution vector at each iteration, can be accelerated by using the projection techniques.     

Combined effects of in-plane boundary conditions and stiffening on buckling of eccentrically stringer-stiffened cylindrical panels

Donnel type stability equations for buckling of stringer stiffened cylindrical panels under combined axial compression and hydrostatic pressure are solved by the displacement approach of [6], The solution is employed for a parametric study over a wide range of panel and stringer geometries to evaluate the combined influence of panel configurations and boundary conditions along the straight edges on the buckling behavior of the panel relative to a complete “counter” cylinder (i.e. a cylinder with identical skin and stiffener parameters).

The parametric studies reveal a “sensitivity” to the “weak in shear”, N_x = N_xφ = 0, along the straight edges, SS1 boundary conditions type where the panel buckling loads are always smaller than those predicted for a complete “counter” cylinder. In the case of “classical”, SS3 B.Cs., there always exist values of panel width, 2φ₀, for which ρ = 1, i.e. the panel buckling load equals that of the complete “counter” cylinder. For SS2 and SS4 B.Cs. types, the nature by which the panel critical load approaches that of the complete cylinder appears to be panel configuration dependent.

Utilization of panels for the experimental determination of a complete cylinder buckling load is found to be satisfactory for relatively very lightly and heavily stiffened panels, as well as for short panels, (L/R) = 0.2 and 0.5. Panels of moderate length and stiffening have to be debarred, since they lead to nonconservative buckling load predictions.     

On the large deviations approximation for the stationary distribution of skip-free regulated queueing networks

Large deviations papers like that of Ignatyuk et al. [Russ. Math. Surv. 49 (1994) 41–99] have shown that asymptotically, the stationary distribution of homogeneous regulated networks is of the form

with the coefficient being different in various “boundary influence domains” and also depending on some of these domains on n. In this paper, we focus on the case of constant exponents and on a subclass of networks we call “strongly skip-free” (which includes all Jackson and all two-dimensional skip-free networks). We conjecture that an asymptotic exponent is constant iff it corresponds to a large deviations escape path which progresses gradually (from the origin to the interior) through boundary facets whose dimension always increases by one. Solving the corresponding large deviations problem for our subclass of networks leads to a family of “local large deviation systems” (LLDSs) (for the constant exponents), which are expressed entirely in terms of the cumulant generating function of the network. In this paper, we show that at least for “strongly skip-free” Markovian networks with independent transition processes, the LLDS is closely related to some “local boundary equilibrium systems” (LESs) obtained by retaining from the equilibrium equations only those valid in neighborhoods of the boundary.

Since asymptotic results require typically only that the cumulant generating function is well-defined over an appropriate domain, it is natural to conjecture that these LLDSs will provide the asymptotic constant exponents regardless of any distributional assumptions made on the network.

Finally, we outline a practical recipe for combining the local approximations to produce a global large deviations approximation , with the coefficients K_j determined numerically.     

Computational complexity of distributed detection problems with information constraints

For a system consisting of a set of sensors S = {S₁, S₂, …, S_m} and a set of objects O = {O₁, O₂, …, O_n}, there are information constraints given by a relation R S × O such that (S_i, O_j) R if and only if S_i is capable of detecting O_j. Each (S_i, O_j) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (S_i, O_j) R, for all S_i S, O_j O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.     

Finite-element technique for solving problems formulated by Hamilton''s principle

The finite element technique is applied to functional which govern dynamical problems, where time is an independent variable.

The present paper demonstrates improved accuracy in mass-spring-damper systems and exemplifies “rendevous problems” of a “travelling” particle in a medium. The motion is governed by Hamilton's principle. The time interval is fixed.

Functionals are constructed from Hamilton's extended principle and appropriate conditions stating the various constraints.

Initial value problems may be incorporated by writing a functional in accordance with Gurtin's method.

Shape functions are polynomials in time and can be extended to other spatial variables when present.

As a result of a variation to the functional, a system of algebraic (not necessarily linear) equations is formed. This system is solved simultaneously to yield its motion within the boundaries of the given time interval.     

Convergence and instability in PCG methods for bordered systems

Bordered almost block diagonal systems arise from discretizing a linearized first-order system of n ordinary differential equations in a two-point boundary value problem with nonseparated boundary conditions. The discretization may use spline collocation, finite differences, or multiple shooting. After internal condensation, if necessary, the bordered almost block diagonal system reduces to a standard finite difference structure, which can be solved using a preconditioned conjugate gradient method based on a simple matrix splitting technique. This preconditioned conjugate gradient method is “guaranteed” to converge in at most 2n + 1 iterations. We exhibit a significant collection of two-point boundary value problems for which this preconditioned conjugate gradient method is unstable, and hence, convergence is not achieved.     

Two minimum spanning forest algorithms on fixed-size hypercube computers

Two parallel algorithms for finding minimum spanning forest (MSF) of a weighted undirected graph on hypercube computers, consisting of a fixed number of processors, are presented. One algorithm is suited for sparse graphs, the other for dense graphs. Our design strategy is based on successive elimination of non-MSF edges. The input graph is partitioned equally among different processors, which then repeatedly eliminate non-MSF edges and merge results to gradually construct the desired MSF of the entire graph. Low communication overhead is achieved by restricting the message-flow to between the neighboring processors in the hypercube topology. The correctness of our approach is due to a theorem which states that with total-ordered edges, if an edge of an arbitrary subgraph does not belong to its MSF, then it does not belong to the MSF of the entire graph. For a graph of n vertices and m edges, our first algorithm finds an MSF in O(m log m)/p) time using p processors for p ≤ (mlog m)/n(1+log(m/n)). The second algorithm, efficient for dense graphs, requires O(n²/p) time for p≤n/log n.     

Complexities of special matrix multiplication problems

This paper develops optimal algorithms to multiply an n × n symmetric tridiagonal matrix by: (i) an arbitrary n × m matrix using 2nm − m multiplications; (ii) a symmetric tridiagonal matrix using 6n − 7 multiplications; and (iii) a tridiagonal matrix using 7n −8 multiplications. Efficient algorithms are also developed to multiply a tridiagonal matrix by an arbitrary matrix, and to multiply two tridiagonal matrices.