REGULARIZATION TOOLS: A Matlab package for analysis and solution of discrete ill-posed problems

The package REGULARIZATION TOOLS consists of 54 Matlab routines for analysis and solution of discrete ill-posed problems, i.e., systems of linear equations whose coefficient matrix has the properties that its condition number is very large, and its singular values decay gradually to zero. Such problems typically arise in connection with discretization of Fredholm integral equations of the first kind, and similar ill-posed problems. Some form of regularization is always required in order to compute a stabilized solution to discrete ill-posed problems. The purpose of REGULARIZATION TOOLS is to provide the user with easy-to-use routines, based on numerical robust and efficient algorithms, for doing experiments with regularization of discrete ill-posed problems. By means of this package, the user can experiment with different regularization strategies, compare them, and draw conclusions from these experiments that would otherwise require a major programming effert. For discrete ill-posed problems, which are indeed difficult to treat numerically, such an approach is certainly superior to a single black-box routine. This paper describes the underlying theory gives an overview of the package; a complete manual is also available.This work was supported by grants from Augustinus Fonden, Knud Højgaards Fond, and Civ. Ing. Frants Allings Legat.     

Comparing routines for the numerical solution of initial value problems of ordinary differential equations in multiple shooting

Summary The numerical solution of two-point boundary value problems and problems of optimal control by shooting techniques requires integration routines. By solving 15 real-life problems four well-known intergrators are compared relative to reliability, fastness and precision. Hints are given, which routines could be used for a problem.     

Explanation,motivation and question posing routines in university mathematics teachers' pedagogical discourse: a commognitive analysis

This paper investigates the teaching practices used by university mathematics teachers when lecturing, a topic within university mathematics education research which is gaining an increasing interest. In the study, a view of mathematics teaching as a discursive practice is taken, and Sfard's commognitive framework is used to investigate the teaching practices of seven Swedish university mathematics teachers on the topic of functions. The present paper looks at the discourse of mathematics teaching, presenting a categorization of the didactical routines into three categories – explanation, motivation and question posing routines. All of these are present in the discourses of all seven teachers, but within these general categories, a number of different sub-categories of routines are found, used in different ways and to different extent by the various teachers. The explanation routines include known mathematical facts, summary and repetition, different representations, everyday language, and concretization and metaphor; the motivation routines include reference to utility, the nature of mathematics, humour and result focus; and the question posing routines include control questions, asking for facts, enquiries and rhetorical questions. This categorization of question posing routines, for instance, complements those already found in the literature. In addition to providing a valuable insight into the teaching of functions at the university level, the categorizations presented in the study can also be useful for investigating the teaching of other mathematical topics.     

Speeding up IP-based algorithms for constrained quadratic 0–1 optimization

In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum-cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvátal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0–1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions.     

Direct and approximate algorithmic methods for solving self-adjoint elliptic PDEs in three-space dimensions

The numerical implementation of the extended to the limit sparse LDL^T factorization solution methods for three-dimensional self-adjoint elliptic partial differential equations [3] is given. Two FORTRAN routines for the approximate (or exact) factorization of the coefficient matrix and solution of the resulting finite difference equations are supplied. The amount of fill-in terms can be controlled by the user through parameters R1, R2 the limiting case being when the matrix is factorized exactly.     

知识创造行为与组织惯例的演化博弈及其仿真研究

以演化博弈模型为主要理论工具,在对知识创造行为与组织惯例关系予以描述的基础上,构建知识创造行为与组织惯例的演化博弈模型。通过求解复制动态方程,分析不同条件下知识创造行为与组织惯例分别达到演化稳定均衡的策略。研究结果表明:知识创造行为与组织惯例的匹配属于动态、重复博弈过程,参与博弈的预期收益、激励成本、转换成本直接决定演化稳定策略且影响个体对知识创造行为与组织惯例的选择,知识创造行为则倾向以承袭为主的保守策略。演化博弈方法的引入为知识创造行为和组织惯例的研究开辟了全新视角,也为相关领域的进一步探索提供有利的理论支持。     

The maximum balanced subgraph of a signed graph: Applications and solution approaches

The Maximum Balanced Subgraph Problem (MBSP) is the problem of finding a subgraph of a signed graph that is balanced and maximizes the cardinality of its vertex set. This paper is the first one to discuss applications of the MBSP arising in three different research areas: the detection of embedded structures, portfolio analysis in risk management and community structure. The efficient solution of the MBSP is also in the focus of this paper. We discuss pre-processing routines and heuristic solution approaches to the problem. a GRASP metaheuristic is developed and improved versions of a greedy heuristic are discussed. Extensive computational experiments are carried out on a set of instances from the applications previously mentioned as well as on a set of random instances.     

Global optimization of a quadratic functional with quadratic equality constraints

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. While it is obvious that, for a nonempty constraint set, there exists a global minimum cost, a method to determine if a given local solution yields the global minimum cost has not been established. We develop a necessary and sufficient condition that will guarantee that solutions of the optimization problem yield the global minimum cost. This constrained optimization problem occurs naturally in the computation of the phase margin for multivariable control systems. Our results guarantee that numerical routines can be developed that will converge to the global solution for the phase margin.     

A Note on the Discontinuity Problem in Heston's Stochastic Volatility Model

Although quasi‐analytic formulas can be derived for European‐style financial claims in Heston's stochastic volatility model, the inverse Fourier integration involved makes the calculation somewhat complicated. This challenge has puzzled practitioners for many years because most implementations of Heston's formula are not robust, even for customarily‐used Heston parameters, as time to maturity is increased. In this article, a simplified approach is proposed to solve the numerical instability problem inherent to the fundamental solution of the Heston model. Specifically, the solution does not require any additional function or a particular mechanism for most software packages or programming library routines to correctly evaluate Heston's analytics.     

An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem

In this paper we consider the two-dimensional (2D) rectangular packing problem, where a fixed set of items have to be allocated on a single object. Two heuristics, which belong to the class of packing procedures that preserve bottom-left (BL) stability, are hybridised with three meta-heuristic algorithms (genetic algorithms (GA), simulated annealing (SA), naı̈ve evolution (NE)) and local search heuristic (hill-climbing). This study compares the hybrid algorithms in terms of solution quality and computation time on a number of packing problems of different size. In order to show the effectiveness of the design of the different algorithms, their performance is compared to random search (RS) and heuristic packing routines.     

The design of a parallel dense linear algebra software library: Reduction to Hessenberg,tridiagonal, and bidiagonal form

This paper discusses issues in the design of ScaLAPACK, a software library for performing dense linear algebra computations on distributed memory concurrent computers. These issues are illustrated using the ScaLAPACK routines for reducing matrices to Hessenberg, tridiagonal, and bidiagonal forms. These routines are important in the solution of eigenproblems. The paper focuses on how building blocks are used to create higher-level library routines. Results are presented that demonstrate the scalability of the reduction routines. The most commonly-used building blocks used in ScaLAPACK are the sequencing BLAS, the parallel BLAS (PBLAS) and the Basic Linear Algebra Communication Subprograms (BLACS). Each of the matrix reduction algorithms consists of a series of steps in each of which one block column (orpanel), and/or block row, of the matrix is reduced, followed by an update of the portion of the matrix that has not been factorized so far. This latter phase is performed using Level 3 PBLAS operations and contains the bulk of the computation. However, the panel reduction phase involves a significant amount of communication, and is important in determining the scalability of the algorithm. The simplest way to parallelize the panel reduction phase is to replace the BLAS routines appearing in the LAPACK routine (mostly matrix-vector and matrix-matrix multiplications) with the corresponding PBLAS routines. However, in some cases it is possible to reduce communication startup costs by performing the communication necessary for consecutive BLAS operations in a single communication using a BLACS call. Thus, there is a tradeoff between efficiency and software engineering considerations, such as ease of programming and simplicity of code.Research was supported in part by the Applied Mathematical Sciences Research Program of the Office of Energy Research, U.S. Department of Energy, by the Defense Advanced Research Projects Agency under contract DAAL03-91-C-0047, administered by the Army Research Office, and in part by the Center for Research on Parallel Computing.     

<Literal>smt</Literal>: a Matlab toolbox for structured matrices

The full exploitation of the structure of large scale algebraic problems is often crucial for their numerical solution. Matlab is a computational environment which supports sparse matrices, besides full ones, and allows one to add new types of variables (classes) and define the action of arithmetic operators and functions on them. The smt toolbox for Matlab introduces two new classes for circulant and Toeplitz matrices, and implements optimized storage and fast computational routines for them, transparently to the user. The toolbox, available in Netlib, is intended to be easily extensible, and provides a collection of test matrices and a function to compute three circulant preconditioners, to speed up iterative methods for linear systems. Moreover, it incorporates a simple device to add to the toolbox new routines for solving Toeplitz linear systems.     

Algorithms for the design of network topologies with balanced disjoint rings

We define the Balanced Disjoint Rings (BDR) problem as developing a method to partition of the nodes in a network to form a given number of disjoint rings of minimum total link length in such a way that there is almost the same number of nodes in each ring. The BDR problem has potential applications in the design of survivable network structures in telecommunications as well as in the identification of local distribution/collection routes in logistics. The BDR problem can also be considered a generalization of the traveling salesman problem since we are interested in multiple tours instead of a single tour. We develop an efficient heuristic solution methodology that involves various GRASP-based randomized solution construction routines that allow a multi-start framework and a n effective combination of cyclic-exchange and single-move neighborhoods in a local search improvement procedure. The algorithms perform very well in our numerical studies, providing encouraging optimality and lower bound gaps with very reasonable runtimes.     

Fast local search for the maximum independent set problem

Given a graph G=(V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing a single vertex with two others. The second routine can determine in O(mΔ) time (where Δ is the highest degree in the graph) whether there are two solution vertices than can be replaced by a set of three. We also present a more elaborate heuristic that successfully applies local search to find near-optimum solutions to a wide variety of instances. We test our algorithms on instances from the literature as well as on new ones proposed in this paper.     

bc–opt: a branch-and-cut code for mixed integer programs

A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features. Received May 11, 1997 / Revised version received March 8, 1999?Published online June 11, 1999     

New concepts and algorithms for portfolio choice

The paper studies the design of optimal (bond) portfolios taking into account various possible utility functions of an investor. The most prominent model for portfolio optimization was introduced by Markowitz. A real solution in this model can be achieved by quadratic programming routines for mean-variance analysis. Of course, there are many reasons for an investor to prefer other utility criteria than return/variance of return in the Markowitz model. In the last few years, many efficient multiple purpose optimization heuristics have been invented for the needs in optimizing telephone nets, chip layouts, job shop scheduling etc. Some of these heuristics have essential advantages: they are extremely flexible and very easy to implement on computers. One example of such an algorithm is the threshold-accepting algorithm (TA). TA is able to optimize portfolios under nearby arbitrary constraints and subject to nearly every utility function. In particular, the utility functions need neither to be convex, differentiable nor ‘smooth’ in any sense. We implemented TA for bond portfolio optimization with different utility criteria. The algorithms and computational results are presented. Under various utility functions, the ‘best’ portfolios look surprisingly different and have quite different qualities. Thus, for a portfolio manager it might be useful to provide himself with such a ‘multiple-taste’ optimizer in order to be able easily to readjust it according to his own personal utility considerations.     

IFECS—an interactive finite element computing system

The development philosophy and implementation of IFECS (an interactive finite element computing system) is described. The system, written in BASIC-PLUS for the RSTS/E computing system, provides solutions for various classes of stress problems in two dimensions. IFECS contains an automatic mesh generator, solution routines and an interactive means of interrogating the program output. This latter feature provides the user with the means of directly selecting relevant information, rather than having to wade through vast reams of the total output. The system, which may be implemented on a very simple computing configuration, is very easy to use and for many problems reduces the effective solution time to a few hours.     

Safe bounds in linear and mixed-integer linear programming

Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size. Mathematics Subject Classification (2000):primary 90C11, secondary 65G20     

Numerical methods for solving the eigenvalue problem for a positive branch confocal unstable resonator

The resonator problem for a positive branch confocal unstable resonator reduces to a Fredholm homogeneous integral equation of the second kind, whose numerical solution here is based on a sequence of algebraic eigenvalue problems. We compare two algorithms for the solution of an optical resonator problem. These are obtained by (i) successive degenerate kernel approximation by Taylor polynomials of the Fredholm kernel and (ii) Nyström’s method with Simpson’s rule as the subordinate numerical integration method. The numerical results arising from these routines compare well with other published results, and have the added advantage of simplicity and easy adaptability to other resonator problems.