The parallel volume at large distances

In this paper we examine the asymptotic behavior of the parallel volume of planar non-convex bodies as the distance tends to infinity. We show that the difference between the parallel volume of the convex hull of a body and the parallel volume of the body itself tends to 0. This yields a new proof for the fact that a planar body can only have polynomial parallel volume if it is convex. Extensions to Minkowski spaces and random sets are also discussed.     

on hybrid preconditioning methods for large sparse saddle-point problems

Based on the block-triangular product approximation to a 2-by-2 block matrix, a class of hybrid preconditioning methods is designed for accelerating the MINRES method for solving saddle-point problems. The appropriate values for the parameters involved in the new preconditioners are estimated, so that the numerical conditioning and the spectral property of the saddle-point matrix of the linear system can be substantially improved. Several practical hybrid preconditioners and the corresponding preconditioning iterative methods are constructed and studied, too.     

Preconditioning techniques for the iterative solution of scattering problems

We consider a time-harmonic electromagnetic scattering problem for an inhomogeneous medium. Some symmetry hypotheses on the refractive index of the medium and on the electromagnetic fields allow to reduce this problem to a two-dimensional scattering problem. This boundary value problem is defined on an unbounded domain, so its numerical solution cannot be obtained by a straightforward application of usual methods, such as for example finite difference methods, and finite element methods. A possible way to overcome this difficulty is given by an equivalent integral formulation of this problem, where the scattered field can be computed from the solution of a Fredholm integral equation of second kind. The numerical approximation of this problem usually produces large dense linear systems. We consider usual iterative methods for the solution of such linear systems, and we study some preconditioning techniques to improve the efficiency of these methods. We show some numerical results obtained with two well known Krylov subspace methods, i.e., Bi-CGSTAB and GMRES.     

Convergence of parallel multistep hybrid methods for singular perturbation problems

Parallel multistep hybrid methods (PHMs) can be implemented in parallel with two processors, accordingly have almost the same computational speed per integration step as BDF methods of the same order with the same stepsize. But PHMs have better stability properties than BDF methods of the same order for stiff differential equations. In the present paper, we give some results on error analysis of A(α)-stable PHMs for the initial value problems of ordinary differential equations in singular perturbation form. Our convergence results are similar to those of linear multistep methods (such as BDF methods), i.e. the convergence orders are equal to their classical convergence orders, and no order reduction occurs. Some numerical examples also confirm our results.     

Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before submitting them to a branch-and-bound procedure, we reformulate them in such a way that we can ensure convexity and a high-quality continuous lower bound. Experimental results show that this methodology is interesting by obtaining the best results in literature for two of the three studied scheduling problems.     

One-parameter imbedding techniques for the solution of nonlinear boundary-value problems

A powerful numerical tool for the solution of nonlinear boundary-value problems —the one-parameter imbedding technique—is suggested. The basic principle is more than twenty years old; however, its numerical utilization has had only a few restricted applications up until recent times. The methods are divided into two categories: one- and multi-loop techniques. It is shown that the multi-loop techniques are of correct and incorrect type. Based on correct procedures new iteration techniques may be developed. Numerical solutions of differential equations arising for the one-parameter imbedding methods are presented along with the corresponding iteration techniques. Some typical imbedding procedures are discussed, and practical application of the method is demonstrated on calculated examples.     

On the optimal solution of large eigenpair problems

The problem of approximation of an eigenpair of a large n × n matrix A is considered. We study algorithms which approximate an eigenpair of A using the partial information on A given by b, Ab, …, A^jb, j ⪡ n, i.e., by Krylov subspaces. A new algorithm called the generalized minimal residual (gmr) algorithm is analyzed. Its optimality for some classes of matrices is proved. We compare the gmr algorithm with the widely used Lanczos algorithm for symmetric matrices. The gmr and Lanczos algorithms cost essentially the same per step and they have the same stability characteristics. Since the gmr algorithm never requires more steps than the Lanczos algorithm, and sometimes uses substantially fewer steps, the gmr algorithm seems preferable. We indicate how to modify the gmr algorithm in order to approximate p eigenpairs of A. We also show some other problems which can be nearly optimally solved by gmr-type algorithms. The gmr algorithm for symmetric matrices was implemented and some numerical results are described. The detailed implementation, more numerical results, and the Fortran subroutine can be found in Kuczyński (“Implementation of the gmr Algorithm for Large Symmetric Eigenproblems,” Report, Columbia University, 1985). The Fortran subroutine is also available via anonymous FTP as “pub/gmrval” on COLUMBIA-EDU [128.59.16.1] on the Arpanet.     

A multipurpose parallel genetic hybrid algorithm for non-linear non-convex programming problems

The genetic hybrid algorithm (GHA) is a general-purpose algorithm, spanning several areas of mathematical problem solving. GHA makes calls to an (empty) accelerator function at key stages of the solution process, providing it with the current population of solution vectors in the argument list of the function. On return from the accelerator, GHA processes the population further. The user has control over the specific stage (generation of a new population, crossover, mutation etc.) and can modify the population of solution vectors, e.g., by making calls to special purpose algorithms through the accelerator channel. If needed, the steps of GHA can be partly or completely superseded by the special purpose mathematical/artificial intelligence based algorithm. The system can be used as a package for classical mathematical programming with the genetic sub-block deactivated. On the other hand, the algorithm can be turned into a machinery for stochastic analysis (e.g. for Monte Carlo simulation, time series modelling or neural networks), where the mathematical programming and genetic computing facilities are deactivated. Finally, pure evolutionary computation can be activated for studying genetic phenomena. As a completely new feature, we design and implement a flexible multicomputer framework for the basic GHA.     

Adaptive greedy techniques for approximate solution of large RBF systems

For the solution of large sparse linear systems arising from interpolation problems using compactly supported radial basis functions, a class of efficient numerical algorithms is presented. They iteratively select small subsets of the interpolation points and refine the current approximative solution there. Convergence turns out to be linear, and the technique can be generalized to positive definite linear systems in general. A major feature is that the approximations tend to have only a small number of nonzero coefficients, and in this sense the technique is related to greedy algorithms and best n-term approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

OpTiX-II: A software environment for the parallel solution of nonlinear optimization problems

The intention of the paper is to give an introduction to the OpTiX-II Software Environment, which supports the parallel and distributed solution of mathematical nonlinear programming problems. First, a brief summary of nonsequential solution concepts for nonlinear optimization on multiprocessor systems will be given. The focus of attention will be put on coarse-grained parallelization and its implementation on multi-computer clusters. The conceptual design objectives for the OpTiX-II Software Environment will be presented as well as the implementation on a workstation cluster, a transputer system and a multiprocessor workstation (shared memory). The OpTiX-II system supports the steps from the formulation of nonlinear optimization problems to their solution on networks of (parallel) computers. In order to demonstrate the use of OpTiX-II, the solution of a nonlinear optimization problem from the field of structural design is discussed and some numerical test results are supplied.     

Parallel algebraic hybrid solvers for large 3D convection-diffusion problems

In this paper we study the parallel scalability of variants of an algebraic additive Schwarz preconditioner for the solution of large three dimensional convection diffusion problems in a non-overlapping domain decomposition framework. To alleviate the computational cost, both in terms of memory and floating-point complexity, we investigate variants based on a sparse approximation or on mixed 32- and 64-bit calculation. The robustness and the scalability of the preconditioners are investigated through extensive parallel experiments on up to 2,000 processors. Their efficiency from a numerical and parallel performance view point are reported. This research activity was partially supported within the framework of the ANR-CIS project Solstice (ANR-06-CIS6- 010).     

Maximizing the minimum completion time on parallel machines

We propose an exact branch-and-bound algorithm for the problem of maximizing the minimum machine completion time on identical parallel machines. The proposed algorithm is based on tight lower and upper bounds as well as an effective symmetry-breaking branching strategy. Computational results performed on a large set of randomly generated instances attest to the efficacy of the proposed algorithm.      

A hybrid method using wavelets for the numerical solution of boundary value problems on the interval

In this work, various aspects of wavelet-based methods for second order boundary value problems under Galerkin framework are investigated. Based on the B-spline multiresolution analysis (MRA) on the line we propose a hybrid method on the interval which combines different treatments for interior and boundary splines. By using this procedure, the MRA structure was conserved and hierarchical representations of the solution at different scales were obtained without much computational effort. Numerical examples are given to verify the effectiveness of the proposed method and the comparison with other techniques is presented.     

非同类机极小化最大完工时间的保密排序问题

提出并研究了一类非同类机的极小化最大完工时间的保密排序问题Rm||Cmax.该问题的模型参数分为若干组,每个组都由一个不愿意共享或公开自己数据的单位所拥有.基于随机矩阵变换构造了一个不泄露私有数据且与原问题等价的安全规划模型,求解该安全模型可以获得问题的最优解,而且各单位的隐私数据仍然保持不被泄露.     

Improved parallel QR method for large least squares problems involving Kronecker products

A new algorithm is presented for the efficient solution of large least squares problems in which the coefficient matrix of the linear system is a Kronecker product of two smaller dimension matrices. The solution algorithm is based on QR factorizations of the smaller dimension matrices. Near perfect load balancing is achieved by exploiting a ‘commutativity’ property of the Kronecker product, and communication requirements are minimized by employing a binary exchange algorithm for matrix transposition. The parallel algorithm is presented, and timing results are shown from test runs on an Intel i860 computer.