Parallel Cholesky factorization on a shared-memory multiprocessor

A parallel algorithm is developed for Cholesky factorization on a shared-memory multiprocessor. The algorithm is based on self-scheduling of a pool of tasks. The subtasks in several variants of the basic elimination algorithm are analyzed for potential concurrency in terms of precedence relations, work profiles, and processor utilization. This analysis is supported by simulation results. The most promising variant, which we call column-Cholesky, is identified and implemented for the Denelcor HEP multiprocessor. Experimental results are given for this machine.     

Complexity of solution structures in nonlinear pricing

This paper characterizes and enumerates the possible solution structures in nonlinear pricing problem when the number of buyer types is given. It is shown that the single-crossing property, which is a standard assumption in the literature, reduces the complexity of solving the problem dramatically. The number of possible solution structures is important when the pricing problem is solved under limited information.     

Efficient diagonalization of oversized matrices on a distributed-memory multiprocessor

On parallel architectures, Jacobi methods for computing the singular value decomposition (SVD) and the symmetric eigenvalue decomposition (EVD) have been established as one of the most popular algorithms due to their excellent parallelism. Most of the Jacobi algorithms for distributed-memory architectures have been developed under the assumption that matrices can be distributed over the processors by square blocks of an even order or column blocks with an even number of columns. Obviously, there is a limit on the number of processors while we need to deal with problems of various sizes. We propose algorithms to diagonalize oversized matrices on a given distributed-memory multiprocessor with good load balancing and minimal message passing. Performances of the proposed algorithms vary greatly, depending on the relation between the problem size and the number of available processors. We give theoretical performance analyses which suggest the faster algorithm for a given problem size on a given distributed-memory multiprocessor. Finally, we present a new implementation for the convergence test of the algorithms on a distributed-memory multiprocessor and the implementation results of the algorithms on the NCUBE/seven hypercube architecture.This work was supported by National Science Foundation grant CCR-8813493. This work was partly done during the author's visit to the Mathematical Science Section, Engineering Physics and Mathematics Division, Oak Ridge National Laboratory, while participating in the Special Year on Numerical Linear Algebra, 1988, sponsored by the UTK Departments of Computer Science and Mathematics, and the ORNL Algebra sponsored by the UTK Departments of Computer Science and Mathematics, and the ORNL Mathematical Sciences Section, Engineering Physics and Mathematics Division.     

Exact solution of the problem of plane bending of a layered ring

An exact solution is given for the problem of a closed cylindrical transversely isotropic ring subjected to bending in its own plane under an arbitrary external load; it is assumed that a fiber straight before deformation and orthogonal to the neutral surface remains straight and undeformed but may no longer be orthogonal to the neutral surface. A variant of the theory developed by Korolev is employed.Moscow Institute of Electronic Machine Building. Translated from Mekhanika Polimerov, No. 1, pp. 168–171, January–February, 1973.     

Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors

In the classical scheduling theory, it is widely assumed that a task can be processed by only one processor at a time. With the rapid development of technology, this assumption is no longer valid. In this work we present a problem of scheduling tasks, each of which requires for its processing a set of processors simultaneously and which can be executed on several alternative sets of processors. Scheduling algorithms based on dynamic and linear programming are presented that construct minimum length non-preemptive and preemptive schedules, respectively. Results of computational experiments are also reported.This research was partially supported by a KBN grant and by project CRIT.     

Complexity of projective methods for the solution of ill-posed problems

We consider the problem of finite-dimensional approximation for solutions of equations of the first kind and propose a modification of the projective scheme for solving ill-posed problems. We show that this modification allows one to obtain, for many classes of equations of the first kind, the best possible order of accuracy for the Tikhonov regularization by using an amount of information which is far less than for the standard projective technique.     

Complexity and asymptotic stability in the process of biochemical substance exchange in a coupled ring of cells

We have considered the complexity and asymptotic stability in the process of biochemical substance exchange in a coupled ring of cells. We have used coupled maps to model this process. It includes the coupling parameter, cell affinity and environmental factor as master parameters of the model. We have introduced: (i) the Lempel–Ziv complexity spectrum and (ii) the Lempel–Ziv complexity spectrum highest value to analyze the dynamics of two cell model. The asymptotic stability of this dynamical system using an eigenvalue-based method has been considered. Using these complexity measures we have noticed an “island” of low complexity in the space of the master parameters for the weak coupling. We have explored how stability of the equilibrium of the biochemical substance exchange in a multi-cell system (N = 100) is influenced by the changes in the master parameters of the model for the weak and strong coupling. We have found that in highly chaotic conditions there exists space of master parameters for which the process of biochemical substance exchange in a coupled ring of cells is stable.     

Complexity of solution of linear systems in rings of differential operators

Suppose given a k₁×k₂ system of linear equations over the Weyl algebraA _n = F[X₁,...X₁,D₄,...,D_n] or over the algebra of differential operatorsK _n = F[X₁,...X₁,D₄,...,D_n], where the degree of each coefficient of the system is less than d. It is proved that if the system is solvable overA _n, orK _n, respectively, then it has a solution of degree at most (k, d)²⁰⁽ⁿ⁾.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 47–59, 1991.     

Planning computations in a multiprocessor system with unfixed parameters

The problem of constructing a feasible preemptive multiprocessor schedule is considered for a case where directive intervals are assigned, processors can have arbitrary performance, and the amount of tasks depends linearly on the volume of additional resources allocated for them. In cases where a feasible schedule is not found with an allocated volume of additional resources, the problem of optimally correcting the directive intervals is considered. The solution is based on an analysis of the necessary and sufficient conditions of a feasible schedule’s existence.     

Sorting on a ring of processors

We study the time necessary to sort on a ring of processors. We show that the amount of space available to each processor determines the time required. We prove a lower bound of 2[n/2] − 1 steps for sorting on a ring of n processors, under the constraint that each processor retains only a single value at any time. In contrast, we show an algorithm that sorts in [n/2] + 1 steps if each processor is allowed to store six values.     

Distributed termination on a ring

The termination detection problem of a distributed computation has gained considerable interest recently. In this paper two symmetric solutions to this problem are presented in the special case, where the distributed computation is performed by a ring of processes. We shall discuss the problem in terms of processes communicating via shared variables instead of messages.     

Numerical simulation of spatially unsteady jets of compressible gas on a multiprocessor computer system

Vortex structures in subsonic and transonic jets of various initial profiles are numerically simulated. The mathematical models are based on conservative finite difference schemes that approximate conservation laws in the framework of the model of nonviscous perfect gas. The unsteady vortex structures are visualized. Pulsating characteristics of the flow are examined and compared with experimental data. Computations are performed using parallel algorithms implemented on a cluster architecture system. The influence of the parallelization scheme and the number of computing units on the performance of the algorithms is investigated. The approximation errors of real-life computations are estimated using the differential approximation method.     

Complexity of a knot invariant

The algebraic structures called quandles constitute a complete invariant for tame knots. However, determining when two quandles are isomorphic is an empirically hard problem, so there is some dissatisfaction with quandles as knot invariants. We have confirmed this apparent difficulty, showing within the framework of Borel reducibility that the general isomorphism problem for quandles is as complex as possible. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On diagnosability of large multiprocessor networks

We consider problems of fault diagnosis in multiprocessor systems. Preparata, Metze and Chien [F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Comput. EC 16 (12) (1967) 848-854] introduced a graph theoretical model for system-level diagnosis, in which processors perform tests on one another via links in the system. Fault-free processors correctly identify the status of tested processors, while the faulty processors can give arbitrary test results. The goal is to identify faulty processors based on the test results. A system is said to be t-diagnosable if faulty units can be identified, provided the number of faulty units present does not exceed t. We explore here diagnosis problems for n-cube systems and give bounds for diagnosability of the n-cube. We also describe a simple diagnosis algorithm A which is linear in time and which can be used for sequential diagnosis as well as for incomplete diagnosis in one step. In particular, the algorithm applied to arbitrary topology based interconnection systems G with N processors improves previously known ones. It has sequential diagnosability , which is optimal in the worst case.     

Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard

In 1954, Johnson gave an efficient algorithm for minimizing makespan in a two-machine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule of 1959 finds a shortest preemptive schedule on identical parallel machines in linear time. A similarly efficient algorithm is unlikely to exist for the simplest common generalization of these problems. We show that preemptive scheduling in a two-stage flow shop with at least two identical parallel machines in one of the stages so as to minimize makespan is NP-hard in the strong sense.     

Solution of three-dimensional problems of gas dynamics on multiprocessor computers

We give the results of solving a number of three-dimensional nonstationary problems of gas dynamics, whose programmatic implementation on multiprocessor computers is carried out using the NORMA language. We compare the effectiveness of different computing systems. Nine figures. Bibliography: 9 titles. Translated fromMetody Matematicheskoi Fiziki, 1998, pp. 172–183.