The 0—1 Integer Programming Problem in a finite ring with identity

We define the 0—1 Integer Programming Problem in a finite field or finite ring with identity as: given an m × n matrix A and an n × 1 vector b with entries in the ring R, find or determine the non-existence of a 0—1 vector x such that Ax = b. We give an easily implemented enumerative algorithm for solving this problem, along with conditions that spurious solutions occur with probability as small as desired. Finally, we show that the problem is NP-complete if R is the ring of integers modulo r for r ≥ 3. This result suggests that it will be difficult to improve on our algorithm.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

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.     

An algorithm for computing the distance to uncontrollability

In this paper, we present an algorithm to compute the distance to uncontrollability. The problem of computing the distance is an optimization problem of minimizing σ(x,y) over the complete plane. This new approach is based on finding zero points of grad σ(x,y ). We obtain the explicit expression of the derivative matrix of grad σ(x,y). The Newton's method and the bisection method are applied to approach these zero points. Numerical results show that these methods work well.     

Optimal and nearly optimal algorithms for approximating polynomial zeros

We substantially improve the known algorithms for approximating all the complex zeros of an n^th degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schönhage [1], Pan [2], and Neff and Reif [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable x has been scaled so as to confine the zeros of p(x) to the unit disc x : |x| ≤ 1, our algorithms (which promise to be practically effective) approximate all the zeros of p(x) within the absolute error bound 2^−b, by using order of n arithmetic operations and order of (b + n)n² Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n² Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).     

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.     

On the latent roots of λ matrices

In this paper we consider equations defined by (1.3)–(1.2)–(1.4). We describe in detail three algorithms for the approximate determination of |λ_nr|, for |λ₁| resp. for one of the λ_j's. The single steps of the algorithms are the four fundamental operations and the positive value of k^th roots of positive numbers and the main interest of them lies in the fact that (the algorithms themselves and so) their lengths depend only on n, r and the prescribed relative error and not on the entries of the matrices A_ν.     

A systolic algorithm for solving dense linear systems

For an arbitrary n × n matrix A and an n × 1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax = b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 ≤ i ≤ n, the i^th linear array is responsible to eliminate the i^th unknown variable x_i of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover, this algorithm can detect whether A is singular or not.     

High-dimensional homotopy curve tracking on a shared-memory multiprocessor

Results are reported for a series of experiments involving numerical curve tracking on a shared-memory parallel computer. Several algorithms exist for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, that is, with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then the tracking of some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. A parallel version of HOMPACK is implemented on a shared-memory parallel computer with various levels and degrees of parallelism (e.g., linear algebra, function, and Jacobian matrix evaluation), and a detailed study is presented for each of these levels with respect to the speedup in execution time obtained with the parallelism, the time spent implementing the parallel code, and the extra memory allocated by the parallel algorithm.     

Comparing parallel Newton''s method with parallel Laguerre''s method

Newton's and Laguerre's methods can be used to concurrently refine all separated zeros of a polynomial P(z). This paper analyses the rate convergence of both procedures, and its implication on the attainable number n of correct figures. In two special cases the number m of iterations required to reach an accuracy η = 10⁻ⁿ is shown to grow as log_λ n, where λ = 3 for Newton's and λ = 4 for Laguerre's. In the general case m is shown to grow linearly with n for both procedures. An assessment of the efficiency of the two methods is also given, by evaluating the computational complexity of operations in circular arithmetic, and the efficiency indices of the two iterative schemes.     

Allocating storage in hierarchical data bases using traces

This paper describes a class of methods to allocate a hierarchical (i.e. tree structured) data base using traces. A trace is an n-tuple of indices, [x(1),…, x(n)], which describes the unique path from the root of the tree to the node being addressed. That is, one takes the x(1)-th branch from the root, followed by the (2)-th branch from the next node, etc. until the path is completed. The last node on the path is the one being addressed.

Given a set of traces that represent a set of nodes in a tree, the problem is to allocate them efficiently on a file.We approach the problem by finding ways of mapping n-tuples (i.e. traces) onto natural numbers (i.e. file indices). An allocation scheme is proposed which uses a 1:1, onto trace-to-address map and is designed to adapt to a changing distribution of nodes within the tree. The scheme is an attempt to solve the problem of efficiently allocating growing data bases.     

An asymptotic theory for recurrence relations based on minimization and maximization

We derive asymptotic approximations for the sequence f(n) defined recursively by f(n)=min_1j<n {f(j)+f(n−j)}+g(n), when the asymptotic behavior of g(n) is known. Our tools are general enough and applicable to another sequence F(n)=max_1j<n {F(j)+F(n−j)+min{g(j),g(n−j)}}, also frequently encountered in divide-and-conquer problems. Applications of our results to algorithms, group testing, dichotomous search, etc. are discussed.     

Asymptotic behavior of solutions of asymptotically constant coefficient systems of linear differential equations

Sufficient conditions are given for the n × n system y'=(A+P(t))y to have a solution such that as t → ∞, where λ is an eigenvalue of the constant matrix A and v is an associated eigenvector. The integrability conditions on P allow conditional convergence and the o(1) terms are specified precisely.     

Fast evaluation of radial basis functions: I

This paper describes some new techniques for the rapid evaluation and fitting of radial basic functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = Σ_j=1^N d_jφ(x−x_j), where φ(u) = |u|²log|u|, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision ε, can be cut to O(1+|log ε|) operations. In particular, if A is the interpolation matrix, a_i,j = φ(x_i−x_j, the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N²) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.     

Nonexistence of finite-dimensional filters for conditional statistics of the cubic sensor problem

Consider the cubic sensor dx = dw, dy = x³dt + dv where w, v are two independent Brownian motions. Given a function φ(x) of the state x let φ_t(x) denote the conditional expectation given the observations y_s, 0 s t. This paper consists of a rather detailed discussion and outline of proof of the theorem that for nonconstant φ there cannot exist a recursive finite-dimensional filter for φ driven by the observations.     

Third-order generalization: A new approach to categorizing higher-order generalization

Generalization, in its most basic form, is an artificial neural network's (ANN's) ability to automatically classify data that were not seen during training. This paper presents a framework in which generalization in ANNs is quantified and different types of generalization are viewed as orders. The ordering of generalization is a means of categorizing different behaviours. These orders enable generalization to be evaluated in a detailed and systematic way. The approach used is based on existing definitions which are augmented in this paper. The generalization framework is a hierarchy of categories which directly aligns an ANN's ability to perform table look-up, interpolation, extrapolation, and hyper-extrapolation tasks.

The framework is empirically validated. Validation is undertaken with three different types of regression task: (1) a one-to-one (o–o) task, f(x):x_i→y_j; (2) the second, in its f(x):{x_i,x_i+1, …}→y_j formulation, maps a many-to-one (m–o) task; and (3) the third f(x):x_i→{y_j,y_j+1, …} a one-to-many (o–m) task. The first and second are assigned to feedforward nets, while the third, due to its complexity, is assigned to a recurrent neural net.

Throughout the empirical work, higher-order generalization is validated with reference to the ability of a net to perform symmetrically related or isomorphic functions generated using symmetric transformations (STs) of a net's weights. The transformed weights of a base net (BN) are inherited by a derived net (DN). The inheritance is viewed as the reuse of information. The overall framework is also considered in the light of alignment to neural models; for example, which order (or level) of generalization can be performed by which specific type of neuron model.

The complete framework may not be applicable to all neural models; in fact, some orders may be special cases which apply only to specific neuron models. This is, indeed, shown to be the case. Lower-order generalization is viewed as a general case and is applicable to all neuron models, whereas higher-order generalization is a particular or special case. This paper focuses on initial results; some of the aims have been demonstrated and amplified through the experimental work.     

The application of explicit Nyström methods to singular second order differential equations

An important class of singular second order initial value problems is y″ + (2/x)y′+f(x,y) = 0, 0 < x < x_f, y(0) = a, y′(0) = 0; this class includes, for example, the well-known singular equations of Emden and Liouville. The purpos of this paper is to show the interesting result that explicit Nyström methods, existing for the direct integration of special second order regular initial value problems, can be used for the integration of this class of singular initial value problems and the methods show their proper respective orders of convergence. This is justified mathematically and demonstrated computationally.     

Partial words and a theorem of Fine and Wilf revisited

A word of length n over a finite alphabet A is a map from {0,…,n−1} into A. A partial word of length n over A is a partial map from {0,…,n−1} into A. In the latter case, elements of {0,…,n−1} without image are called holes (a word is just a partial word without holes). In this paper, we extend a fundamental periodicity result on words due to Fine and Wilf to partial words with two or three holes. This study was initiated by Berstel and Boasson for partial words with one hole. Partial words are motivated by molecular biology.