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.     

Linear rotation based algorithm and systolic architecture for solving linear system equations

A linear rotation based algorithm is proposed for solving linear system equations, Ax = b. This algorithm modified the conventional Gaussian elimination method and can avoid the problems of numerical singularity and ill condition. In this study, the implementation of a trapezoidal systolic array of n²/2 + n −2 processors as well as a linear array of n processors are accomplished for this algorithm. The trapezoidal systolic array performs the triangularization of a matrix A by using the modified linear rotation algorithm; while the linear array performs the backward substitution for evaluating the solution of x. The computing time for solving a linear equation system will be O(5n) time units. Also an implicit representation of the elimination factor by means of the sign parameter sequence instead of an numerical value is introduced for simplifying the hardware complexity. It is clear that this systolic architecture is simple, uniform, and regular, and therefore well suitable for the implementation of a VLSI chip.     

Constrained multibody system dynamics an automated approach

The governing equations for constrained multibody systems are formulated in a manner suitable for their automated, numerical development and solution. Specifically, the “closed loop” problem of multibody chain systems is addressed.

The governing equations are developed by modifying dynamical equations obtained from Lagrange's form of d'Alembert's principle. This modification, which is based upon a solution of the constraint equations obtained through a “zero eigenvalues theorem,” is, in effect, a contraction of the dynamical equations.

It is observed that, for a system with n generalized coordinates and m constraint equations, the coefficients in the constraint equations may be viewed as “constraint vectors” in n-dimensional space. Then, in this setting the system itself is free to move in the n−m directions which are “orthogonal” to the constraint vectors.     

Spacetime-minimal systolic arrays for Gaussian elimination and the Algebraic path problem

In this paper, we derive time-minimal systolic arrays for Gaussian elimination and the Algebraic Path Problem (APP) that use a minimal number of processors. For a problem of size n, we obtain an execution time T(n) = 3n −1 using A(n) = n²/4+O(n) processors for Gaussian elimination, and T(n) = 5n −2 and A(n) = n³/+O(n) for the APP.     

A design of time-optimum and register-number-minimum systolic convolvers

We present an optimum bit-parallel/word-sequential systolic convolver. Our design is the best one among the previous many convolvers in the sense that its optimality in time and space performances is simultaneously attained without augmenting any global control, broadcasting, initial-data-preloading, and/or multi-sequential or parallel I/O ports which were allowed in most of the previous designs. As an application of our convolver we give a systolic polynomial divider which can compute the polynomial division in exactly n + O(1) optimum steps on [min(n−m, m)/2]+O(1) systolic cells for the division of any degree n polynomial by any degree m polynomial (n m).     

Integration of polynomials over n-dimensional linear polyhedra

This paper is concerned with explicit integration formulae for computing integrals of n-variate polynomials over linear polyhedra in n-dimensional space ⁿ. Two different approaches are discussed; the first set of formulae is obtained by mapping the polyhedron in n-dimensional space ⁿ into a standard n-simplex in ⁿ, while the second set of formulae is obtained by reducing the n-dimensional integral to a sum of n − 1 dimensional integrals which are n + 1 in number. These formulae are followed by an application example for which we have explained the detailed computational scheme. The symbolic integration formulae presented in this paper may lead to an easy and systematic incorporation of global properties of solid objects, such as, for example, volume, centre of mass, moments of inertia etc., required in engineering design problems.     

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).     

A parallel residue-to-binary conversion algorithm without trial division

In recent years, the conversion of residue numbers to a binary integer has been intensively studied. The Chinese Remainder Theorem (CRT) is a solution to this conversion problem of a number to the Residue Number System with a general moduli set. This paper presents a new division-free conversion approach for the conversion of residue numbers to a binary integer. The algorithm differs from others employing a great number of division instructions by using shift instructions instead. These simple instructions keep the power consumption lower. This algorithm can also be implemented with a lookup table or upon a vector machine. Both make the conversion process efficient. This division-free algorithm employs the concept of Montgomery multiplication algorithm. There are two variations of Montgomery algorithm proposed, which are algorithms MMA and IMA. The algorithm MMA is to transform the input number into the output presentation of Montgomery algorithm. Algorithm IMA is therefore inverse the computation of Montgomery algorithm to obtain the multiplicand. These two algorithms are in the complexity of O(n), where n is log₂ q_i. q_i is a modulus. The proposed algorithm for converting the residues to a binary integer therefore runs on O(n × log m) times on O(m) processors. There are O(log m) iterations of O(n) complexity. Compared with the traditional conversion algorithm, the advantages of this proposed algorithm are not only in employing simpler operations but also in performing fewer iterations.     

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.     

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.     

The Graph Neural Network Model

Many underlying relationships among data in several areas of science and engineering, e.g., computer vision, molecular chemistry, molecular biology, pattern recognition, and data mining, can be represented in terms of graphs. In this paper, we propose a new neural network model, called graph neural network (GNN) model, that extends existing neural network methods for processing the data represented in graph domains. This GNN model, which can directly process most of the practically useful types of graphs, e.g., acyclic, cyclic, directed, and undirected, implements a function tau(G,n) isin IR^m that maps a graph G and one of its nodes n into an m-dimensional Euclidean space. A supervised learning algorithm is derived to estimate the parameters of the proposed GNN model. The computational cost of the proposed algorithm is also considered. Some experimental results are shown to validate the proposed learning algorithm, and to demonstrate its generalization capabilities.     

Experiments with some cluster analysis algorithms

In this paper, we shall show the following experimental results: (1) the one-dimensional clustering algorithm advocated by Slagle and Lee⁽¹⁾ can be generalized to the n-dimensional case, n > 1: (2) if a set of points in some n-space (n > 1) are linearly ordered through the short spanning path algorithm, then this set of points can be considered as occupying a one-dimensional space and the original n-dimensional clustering problem can now be viewed as a one-dimensional clustering problem; (3) a short spanning path usually contains as much information as a minimal spanning tree; (4) the one-dimensional clustering algorithm can be used to find the long links in a short spanning path or a minimal spanning tree. These long links have to be broken to obtain clusters.     

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.     

Relaxed LMI-Based Stability Conditions for Takagi–Sugeno Fuzzy Control Systems Using Regional-Membership-Function-Shape-Dependent Analysis Approach

This paper presents relaxed stability conditions for Takagi-Sugeno (T-S) fuzzy-model-based control systems. It is assumed that the stability conditions are represented by some inequalities in the form of a p-dimensional fuzzy summation. To investigate the system stability, the inequalities are expanded to n-dimensional fuzzy summation (n ges p). The boundary and regional informations of membership functions are then utilized for relaxation of stability analysis results. Two analysis approaches are proposed in this paper. The first approach is called the global-membership-function-shape-dependent approach, in which the lower and upper bounds of the membership functions, and its products from 2 to n in the full operating domain, are considered in the stability analysis. The second approach is named as the regional-membership-function-shape-dependent approach in which the operating region is partitioned to subregions, and the boundary information of membership functions on each operating subregion is employed to facilitate the stability analysis. In both approaches, by the help of the boundary and/or regional information of the membership functions, some inequality constraints in the form of multidimensional fuzzy summation containing some slack matrices are constructed. Stability conditions in the form of linear matrix inequalities (LMIs) are derived. Numerical examples are given to demonstrate the effectiveness of the proposed stability conditions.     

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.     

New construction of highly nonlinear resilient S-boxes via linear codes

Highly nonlinear resilient functions play a crucial role in nonlinear combiners which are usual hardware oriented stream ciphers. During the past three decades, the main idea of construction of highly nonlinear resilient functions are benefited from concatenating a large number of affine subfunctions. However, these resilient functions as core component of ciphers usually suffered from the guess and determine attack or algebraic attack since the n-variable nonlinear Boolean functions can be easily given rise to partial linear relations by fixing at most n/2 variables of them. How to design highly nonlinear resilient functions (S-boxes) without concatenating a large number of n/2 variables affine subfunctions appears to be an important task. In this article, a new construction of highly nonlinear resilient functions is proposed. These functions consist of two classes subfunctions. More specially, the first class (nonlinear part) contains both the bent functions with 2 k variables and some affine subfunctions with n/2 − k variables which are attained by using [ n/2 − k, m, d] disjoint linear codes. The second class (linear part) includes some linear subfunctions with n/2 variables which are attained by using [ n/2, m, d] disjoint linear codes. It is illustrated that these resilient functions have high nonlinearity and high algebraic degree. In particular, It is different from previous well-known resilient S-boxes, these new S-boxes cannot be directly decomposed into some affine subfunctions with n/2 variables by fixing at most n/2 variables. It means that the S-boxes (vectorial Boolean functions) which use these resilient functions as component functions have more favourable cryptography properties against the guess and determine attack or algebraic attacks.     

Computing multidimensional Delaunay tessellations

We recall some properties of Voronoi and Delaunay tessellations in any numbers of dimensions. We then propose a solution to the following problem: Given the Delaunay tessellation of n d-dimensional data points X₁,…, X_n, the proble is to insert a new data point X and to update the tessellation accordingly. The solution proposed achieves minimum space-complexity.     

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)^m) time dynamic programming algorithm and an O(mk^k+1P^2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.     

Pole assignment for multi-input multi-output systems using output feedback

In this paper the problem of pole assignment using constant gain output feedback is studied for MIMO system with system order n > m + l − 1, where m and l are the number of inputs and outputs, respectively. A new procedure is presented to design a constant gain output feedback matrix which assigns (m + l − 2) poles exactly to the desired locations and shifts all the unassigned poles to suitable locations using root locus techniques.