Novel modifications of parallel Jacobi algorithms

We describe two main classes of one-sided trigonometric and hyperbolic Jacobi-type algorithms for computing eigenvalues and eigenvectors of Hermitian matrices. These types of algorithms exhibit significant advantages over many other eigenvalue algorithms. If the matrices permit, both types of algorithms compute the eigenvalues and eigenvectors with high relative accuracy. We present novel parallelization techniques for both trigonometric and hyperbolic classes of algorithms, as well as some new ideas on how pivoting in each cycle of the algorithm can improve the speed of the parallel one-sided algorithms. These parallelization approaches are applicable to both distributed-memory and shared-memory machines. The numerical testing performed indicates that the hyperbolic algorithms may be superior to the trigonometric ones, although, in theory, the latter seem more natural.     

An asynchronous parallel newton method

A parallel Newton method is described for the minimization of a twice continuously differentiable uniformly convex functionF(x). The algorithm generates a sequence {x _j } which converges superlinearly to the global minimizer ofF(x).     

On parallel asynchronous high-order solutions of parabolic PDEs

In achieving significant speed-up on parallel machines, a major obstacle is the overhead associated with synchronizing the concurrent processes. This paper presents high-orderparallel asynchronous schemes, which are schemes that are specifically designed to minimize the associated synchronization overhead of a parallel machine in solving parabolic PDEs. They are asynchronous in the sense that each processor is allowed to advance at its own speed. Thus, these schemes are suitable for single (or multi) user shared memory or (message passing) MIMD multiprocessors. Our approach is demonstrated for the solution of the multidimensional heat equation, of which we present a spatial second-order Parametric Asynchronous Finite-Difference (PAFD) scheme. The well-known synchronous schemes are obtained as its special cases. This is a generalization and expansion of the results in [5] and [7]. The consistency, stability and convergence of this scheme are investigated in detail. Numerical tests show that although PAFD provides the desired order of accuracy, its efficiency is inadequate when performed on each grid point.In an alternative approach that uses domain decomposition, the problem domain is divided among the processors. Each processor computes its subdomain mostly independently, while the PAFD scheme provides the solutions at the subdomains' boundaries. We use high-order finite-difference implicit scheme within each subdomain and determine the values at subdomains' boundaries by the PAFD scheme. Moreover, in order to allow larger time-step, we use remote neighbors' values rather than those of the immediate neighbors. Numerical tests show that this approach provides high efficiency and in the case which uses remote neighbors' values an almost linear speedup is achieved. Schemes similar to the PAFD can be developed for other types of equations [3].This research was supported by the fund for promotion of research at the Technion.     

A parallel asynchronous Newton algorithm for unconstrained optimization

A new approach to the solution of unconstrained optimization problems is introduced. It is based on the exploitation of parallel computation techniques and in particular on an asynchronous communication model for the data exchange among concurrent processes. The proposed approach arises by interpreting the Newton method as being composed of a set of iterative and independent tasks that can be mapped onto a parallel computing system for the execution.Numerical experiments on the resulting algorithm have been carried out to compare parallel versions using synchronous and asynchronous communication mechanisms in order to assess the benefits of the proposed approach on a variety of parallel computing architectures. It is pointed out that the proposed asynchronous Newton algorithm is preferable for medium and large-scale problems, in the context of both distributed and shared memory architectures.This research work was partially supported by the National Research Council of Italy, within the special project Sistemi Informatici e Calcolo Parallelo, under CNR Contract No. 90.00675.PF69.     

Real hypersurfaces in complex two-plane grassmannians with parallel structure Jacobi operator

We give some non-existence theorems for Hopf real hypersurfaces in complex two-plane Grassmannians G ₂(? ^m+2) with parallel structure Jacobi operator R _ξ.     

Performance analysis of automatic assembly systems with in-line parallel stations

An automatic assembly system—a key tool for mass production—isgenerally composed of a number of workstations and a transportsystem. One common problem associated with automatic assemblysystems is that some assembly operations may have relativelylong cycle times. As a consequence, productivity, which is determinedby the operations with the longest cycle time, can be reducedsignificantly. Therefore a special form of parallel workstationknown as an in-line parallel (tandem-gated) station was developedto improve the performance of an automatic assembly system.In this design, stations working in parallel are installed ina serial structure and perform identical operations. Thus, morethan one assembly may be processed simultaneously—a typeof design especially beneficial when a stage requires a longoperation cycle time. A typical example is a computer assemblysystem which performs long inspection operations to ensure thatthe quality level of each product is up to the acceptance level. In this paper, we describe a simulation study of the performancecharacteristics of this type of system, with a statistical analysisof each decision factor. Phenomena affecting the performanceof in-line parallel stations, identified by the assistance ofthe computer graphical display, will then be discussed. An analyticalmodel based on these phenomena identified is then developed.The results generated by the analytical model developed arevalidated by comparisons with the simulation results. Finally,guidelines for optimization of buffer size are presented.     

Real hypersurfaces in the complex quadric with parallel normal Jacobi operator

First we introduce the notion of parallel normal Jacobi operator for real hypersurfaces in the complex quadric . Next we give a complete classification of real hypersurfaces in the complex quadric with parallel normal Jacobi operator.     

Convergence and numerical results for a parallel asynchronous quasi-Newton method

During the execution of a parallel asynchronous iterative algorithm, each task does not wait for predetermined data to become available. On the contrary, they can be viewed as local and independent iterative algorithms, which perform their own iterative scheme on the data currently available.On the basis of this computational model, a parallel asynchronous version of the quasi-Newton method for solving unconstrained optimization problems is proposed. The algorithm is based on four tasks concurrently executing and interacting in an asynchronous way.Convergence conditions are established and numerical results are presented which prove the effectiveness of the proposed parallel asynchronous approach.This research work was partially supported by the National Research Council of Italy within the special project Sistemi Informatici e Calcolo Parallelo under CNR Contract No. 92.01585.PF69.The authors are grateful to M. Al-Baali and R. H. Byrd for their valuable comments.     

Multi-sweep asynchronous parallel successive overrelaxation for the nonsymmetric linear complementarity problem

Convergence is established for themulti-sweep asynchronous parallel successive overrelaxation (SOR) algorithm for thenonsymmetric linear complementarity problem. The algorithm was originally introduced in [4] for the symmetric linear complementarity problem. Computational tests show the superiority of the multi-sweep asynchronous SOR algorithm over its single-sweep counterpart on both symmetric and nonsymmetric linear complementarity problems.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228, and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0124.     

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem

As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.     

Spectral properties of Jacobi matrices by asymptotic analysis

We consider two classes of Jacobi matrix operators in l² with zero diagonals and with weights of the form n^α+c_n for 0<α1 or of the form n^α+c_nn^α−1 for α>1, where {c_n} is periodic. We study spectral properties of these operators (especially for even periods), and we find asymptotics of some of their generalized eigensolutions. This analysis is based on some discrete versions of the Levinson theorem, which are also proved in the paper and may be of independent interest.     

A class of asynchronous parallel nonlinear accelerated overrelaxation methods for the nonlinear complementarity problems

In accordance with the principle of using sufficiently the delayed information, and by making use of the nonlinear multisplitting and the nonlinear relaxation techniques, we present in this paper a class of asynchronous parallel nonlinear multisplitting accelerated overrelaxation (AOR) methods for solving the large sparse nonlinear complementarity problems on the high-speed MIMD multiprocessor systems. These new methods, in particular, include the so-called asynchronous parallel nonlinear multisplitting AOR-Newton method, the asynchronous parallel nonlinear multisplitting AOR-chord method and the asynchronous parallel nonlinear multisplitting AOR-Steffensen method. Under suitable constraints on the nonlinear multisplitting and the relaxation parameters, we establish the local convergence theory of this class of new methods when the Jacobi matrix of the involved nonlinear mapping at the solution point of the nonlinear complementarity problem is an H-matrix.     

Harmonic analysis operators related to symmetrized Jacobi expansions

Following a symmetrization procedure proposed recently by Nowak and Stempak, we consider the setting of symmetrized Jacobi expansions. In this framework we investigate mapping properties of several fundamental harmonic analysis operators, including Riesz transforms, Poisson semigroup maximal operator, Littlewood–Paley–Stein square functions and multipliers of Laplace and Laplace–Stieltjes transform type. Our paper delivers also some new results in the original setting of classical Jacobi expansions.     

Error analysis of Jacobi derivative estimators for noisy signals

Recent algebraic parametric estimation techniques (see Fliess and Sira-Ramírez, ESAIM Control Optim Calc Variat 9:151–168, 2003, 2008) led to point-wise derivative estimates by using only the iterated integral of a noisy observation signal (see Mboup et al. 2007, Numer Algorithms 50(4):439–467, 2009). In this paper, we extend such differentiation methods by providing a larger choice of parameters in these integrals: they can be reals. For this, the extension is done via a truncated Jacobi orthogonal series expansion. Then, the noise error contribution of these derivative estimations is investigated: after proving the existence of such integral with a stochastic process noise, their statistical properties (mean value, variance and covariance) are analyzed. In particular, the following important results are obtained:

Jacobi temperature

The Poisson-Jacobi transform of a function ? defined by $$v(n,t) = \sum\limits_{m = 0}^\infty {h(n,m;t)\phi (m)h_{\alpha ,\beta } } (m)$$ is considered. A theorem for the Jacobi temperaturev (n, t) is established which is analogous to that due to Tychnoff¹ for ordinary temperatures. Its Huygens property and growth pattern are also discussed. A representation theory for Poisson-Jacobi transforms is developed.