外推瀑布式多网格法的OpenMP并行化

基于外推瀑布式多网格法(EXCMG)程序的性能分析, 采用共享存储编程标准OpenMP对EXCMG法的Fortran程序进行了并行处理,极大地提高了原串行程序的计算效率.在双核PC机和机群的一个八核SMP节点上分别进行了数值试验.结果表明: 在不改变串行程序结构的前提下, 仅对EXCMG程序中最耗时的三个子程序并行处理, 双核下并行效率可高达90%;八核下两分钟内可求解上亿个未知数的椭圆边值问题, 精度达到10^-10.     

Fortran codes for computing the discrete Helmholtz integral operators

In this paper Fortran subroutines for the evaluation of the discrete form of the Helmholtz integral operators L _k, M _k, M _k ^t and N _k for two-dimensional, three-dimensional and three-dimensional axisymmetric problems are described. The subroutines are useful in the solution of Helmholtz problems via boundary element and related methods. The subroutines have been designed to be easy to use, reliable and efficient. The subroutines are also flexible in that the quadrature rule is defined as a parameter and the library functions (such as the Hankel, exponential and square root functions) are called from external routines. The subroutines are demonstrated on test problems arising from the solution of the Neumann problem exterior to a closed boundary via the Burton and Miller equation. This revised version was published online in August 2006 with corrections to the Cover Date.     

An iterative back substitution algorithm for the solution of tridiagonal matrix systems with fringes

For tridiagonal matrix systems, a simple direct algorithm giving the solution exists, but in the most general case of tridiagonal matrix with fringes, the direct solving algorithms are more complicated. For big systems, direct methods are not well fitted and iterative algorithms are preferable. In this paper a relaxation type iterative algorithm is presented. It is an extension of the backward substitution method used for simple tridiagonal matrix systems. The performances show that this algorithm is a good compromise between a direct method and other iterative methods as block SOR. Its nature suggests its use as inner solver in the solution of problems derived by application of a decomposition domain method. A special emphasis is done on the programming aspect. The solving Fortran subroutines implementing the algorithm have been generated automatically from their specification by using a computer algebra system technique.     

A Test Set for stiff Initial Value Problem Solvers in the open source software R: Package deTestSet

In this paper we present the R package deTestSet that includes challenging test problems written as ordinary differential equations (ODEs), differential algebraic equations (DAEs) of index up to 3 and implicit differential equations (IDEs). In addition it includes 6 new codes to solve initial value problems (IVPs). The R package is derived from the Test Set for Initial Value Problem Solvers available at http://www.dm.uniba.it/~testset which includes documentation of the test problems, experimental results from a number of proven solvers, and Fortran subroutines providing a common interface to the defining problem functions. Many of these facilities are now available in the R package deTestSet, which comprises an R interface to the test problems and to most of the Fortran solvers. The package deTestSet is free software which is distributed under the GNU General Public License, as part of the R open source software project.     

The Use of Mixed Prolog/Fortran for Battle Simulation

This paper describes the results of a study of the feasbility and cost- effectiveness of using mixed Prolog/Fortran programming to develop flexible, reconfigurable battle simulations, replacing large Fortran programmes which are difficult to modify. A mixed-system architecture is developed, in which Fortran and Prolog are each used to best advantage, and which allows discrete events to be combined with pseudo-continuous processes. The architecture is analysed in terms of a number of performance metrics. The paper concludes that the mixed architecture is feasible, practicable and brings a variety of benefits.     

Computational experience with a group theoretic integer programming algorithm

This paper gives specific computational details and experience with a group theoretic integer programming algorithm. Included among the subroutines are a matrix reduction scheme for obtaining group representations, network algorithms for solving group optimization problems, and a branch and bound search for finding optimal integer programming solutions. The innovative subroutines are shown to be efficient to compute and effective in finding good integer programming solutions and providing strong lower bounds for the branch and bound search.This research was supported in part by the U.S. Army Research Office (Durham) under contract no. DAHC04-70-C-0058. This paper is not an official National Bureau of Economic Research publication.     

Concave minimization via conical partitions and polyhedral outer approximation

An algorithm is proposed for globally minimizing a concave function over a compact convex set. This algorithm combines typical branch-and-bound elements like partitioning, bounding and deletion with suitably introduced cuts in such a way that the computationally most expensive subroutines of previous methods are avoided. In each step, essentially only few linear programming problems have to be solved. Some preliminary computational results are reported.Parts of the present paper were accomplished while the author was on leave at the University of Florida.Parts of the present paper were completed while the author was on leave at the University of Trier as a fellow of the Alexander von Humboldt foundation.     

An algorithm for smoothing,differentiation and integration of experimental data using spline functions

This paper presents an algorithm for fitting a smoothing spline function to a set of experimental or tabulated data. The obtained spline approximation can be used for differentiation and integration of the given discrete function. Because of the ease of computation and the good conditioning properties we use normalised B-splines to represent the smoothing spline. A Fortran implementation of the algorithm is given.     

Numerical recipes for the high efficient inverse of the confluent Vandermonde matrices

In this paper, we derive a numerical recipe for the calculation of the inversion of the confluent Vandermonde matrix. The main result of this article does not require any symbolic calculations and therefore can be performed by a numerical algorithm implemented either in any high level (like Matlab or Mathematica) or low level programming language (C/C++/Java/Pascal/Fortran, etc.). The computational complexity of the presented algorithm is of an O(N²) class being, by the linear term, better than the ordinary Gauss elimination method. Moreover, a ready to use C++ full implementation of the algorithm is attached.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.     

A tolerant algorithm for linearly constrained optimization calculations

Two extreme techniques when choosing a search direction in a linearly constrained optimization calculation are to take account of all the constraints or to use an active set method that satisfies selected constraints as equations, the remaining constraints being ignored. We prefer an intermediate method that treats all inequality constraints with small residuals as inequalities with zero right hand sides and that disregards the other inequality conditions. Thus the step along the search direction is not restricted by any constraints with small residuals, which can help efficiency greatly, particularly when some constraints are nearly degenerate. We study the implementation, convergence properties and performance of an algorithm that employs this idea. The implementation considerations include the choice and automatic adjustment of the tolerance that defines the small residuals, the calculation of the search directions, and the updating of second derivative approximations. The main convergence theorem imposes no conditions on the constraints except for boundedness of the feasible region. The numerical results indicate that a Fortran implementation of our algorithm is much more reliable than the software that was tested by Hock and Schittkowski (1981). Therefore the algorithm seems to be very suitable for general use, and it is particularly appropriate for semi-infinite programming calculations that have many linear constraints that come from discretizations of continua.     

Convex optimization problems involving finite autocorrelation sequences

 We discuss convex optimization problems in which some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback: to represent an autocorrelation sequence of length $n$, it requires the introduction of a large number ($n(n+1)/2$) of auxiliary variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear inequalities. Received: August 20, 2001 / Accepted: July 16, 2002 Published online: September 27, 2002 RID="★" ID="★" This material is based upon work supported by the National Science Foundation under Grant No. ECS-9733450.     

A relaxed cutting plane method for semi-infinite semi-definite programming

In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm.     

An ordering (enumerative) algorithm for nonlinear 0-1 programming

In this paper, a new algorithm to solve a general 0–1 programming problem with linear objective function is developed. Computational experiences are carried out on problems where the constraints are inequalities on polynomials. The solution of the original problem is equivalent with the solution of a sequence of set packing problems with special constraint sets. The solution of these set packing problems is equivalent with the ordering of the binary vectors according to their objective function value. An algorithm is developed to generate this order in a dynamic way. The main tool of the algorithm is a tree which represents the desired order of the generated binary vectors. The method can be applied to the multi-knapsack type nonlinear 0–1 programming problem. Large problems of this type up to 500 variables have been solved.     

Aspects of CXXR internals

The CXXR project aims gradually to refactor the fundamental parts of the R interpreter from C into C++ whilst retaining the full functionality of the standard distribution of R. It is hoped that this will enable researchers more easily to enhance the functionality of R by allowing them to extend the interpreter’s internal C++ class hierarchy. The paper summarises progress to date and describes key aspects of the internal implementation of the CXXR where this differs from the standard interpreter. It also explains stratagems used to facilitate updating CXXR to reflect a new release of R, and examines the relative performance of CXXR and the standard interpreter.     

A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems

This paper presents a primal-dual conjugate subgradient algorithm for solving convex programming problems. The motivation, however, is to employ it for solving specially structured or decomposable linear programming problems. The algorithm coordinates a primal penalty function and a Lagrangian dual function, in order to generate a (geometrically) convergent sequence of primal and dual iterates. Several refinements are discussed to improve the performance of the algorithm. These are tested on some network problems, with side constraints and variables, faced by the Freight Equipment Management Program of the Association of American Railroads, and suggestions are made for implementation.This research was supported by the Association of American Railroads.     

A normalized algorithm for the solution of sparse symmetric seven-diagonal linear systems of semi-bandwidths M and P

In a recent paper [3] normalized factorization procedures for the solution of self-adjoint elliptic partial differential equations in three space dimensions are introduced. In this procedure the coefficient matrix derived from the finite difference discretization of p.d.e.'s is factorized exactly to yield a normalized direct method of solution. The numerical implementation of the algorithm is presented in this paper and FORTRAN subroutines for the efficient solution of the resulting large sparse symmetric seven-diagonal systems are given.     

Projection and restriction methods in geometric programming and related problems

Mathematical programming problems with unattained infima or unbounded optimal solution sets are dual to problems which lackinterior points, e.g., problems for which the Slater condition fails to hold or for which the hypothesis of Fenchel's theorem fails to hold. In such cases, it is possible to project the unbounded problem onto a subspace and to restrict the dual problem to an affine set so that the infima are not altered. After a finite sequence of such projections and restrictions, dual problems are obtained which have bounded optimal solution sets andinterior points. Although results of this kind have occasionally been used in other contexts, it is in geometric programming (both in the original psynomial form and the generalized form) where such methods appear most useful. In this paper, we present a treatment of dual projection and restriction methods developed in terms of dual generalized geometric programming problems. Analogous results are given for Fenchel and ordinary dual problems.This research was supported in part by Grant No. AFOSR-73-2516 from the Air Force Office of Scientific Research and by Grant No. NSF-ENG-76-10260 from the National Science Foundation.The authors wish to express their appreciation to the referees for several helpful comments.