Minimizing synchronization in IDR (s)

IDR (s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are investigated for alleviating this bottleneck. First, a recently proposed IDR (s) algorithm that is highly efficient and stable is reformulated in such a way that it has a single global synchronization point per iteration step. Second, the so‐called test matrix is chosen so that the work, communication, and storage involving this matrix is minimized in multi‐cluster environments. Finally, a methodology is presented for a‐priori estimation of the optimal value of s using only problem and machine‐based parameters. Numerical experiments applied to a 3D convection–diffusion problem are performed on the DAS‐3 Grid computer, demonstrating the effectiveness of our approach. Copyright © 2011 John Wiley & Sons, Ltd.     

A method of iterative data refinement and its applications

Iterative data refinement (IDR) is a general procedure for producing a sequence of estimates of the data that would be collected by a measuring device which is idealized to a certain extent, starting from the data that are collected by an actual measuring device. Following a discussion of the fundamentals of IDR, we present a number of previously published procedures which are special cases of it. We concentrate on examples from medical imaging. In particular, we discuss beam hardening correction in x-ray computerized tomography, attenuation correction in emission computerized tomography, and compensation for missing data in reconstruction from projections. We also show that a standard method of numerical mathematics (the parallel chord method) as well as a whole family of constrained iterative restoration algorithms are special cases of IDR. Thus IDR provides a common framework within which a number of originally different looking procedures are presented and discussed. We also present a result of theoretical nature concerning the initial behavior of IDR.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Micro‐Mechanical Modelling of the Constitutive Behaviour of NiTi Shape Memory Alloys

The superelasticity and shape memory effect in NiTi alloys are examined on the basis of micromechanics within the energy minimization framework. We describe the behaviour of polycrystalline shape‐memory alloys via orientation‐distribution of the various martensite‐variants (domains) present in the material. Stress‐strain curves are presented and special attention is payed to the volume fraction of martensite for specific NiTi alloys (Nitinol) specimen under uniaxial tension. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

New variants of bundle methods

In this paper we describe a number of new variants of bundle methods for nonsmooth unconstrained and constrained convex optimization, convex—concave games and variational inequalities. We outline the ideas underlying these methods and present rate-of-convergence estimates.Corresponding author.     

A unified discontinuous Galerkin framework for time integration

We introduce a new discontinuous Galerkin approach for time integration. On the basis of the method of weighted residual, numerical quadratures are employed in the finite element time discretization to account for general nonlinear ordinary differential equations. Many different conditions, including explicit, implicit, and symplectic conditions, are enforced for the test functions in the variational analysis to obtain desirable features of the resulting time‐stepping scheme. The proposed discontinuous Galerkin approach provides a unified framework to derive various time‐stepping schemes, such as low‐order one‐step methods, Runge–Kutta methods, and multistep methods. On the basis of the proposed framework, several explicit Runge–Kutta methods of different orders are constructed. The derivation of symplectic Runge–Kutta methods has also been realized. The proposed framework allows the optimization of new schemes in terms of several characteristics, such as accuracy, sparseness, and stability. The accuracy optimization is performed on the basis of an analytical form of the error estimation function for a linear test initial value problem. Schemes with higher formal order of accuracy are found to provide more accurate solutions. We have also explored the optimization potential of sparseness, which is related to the general compressive sensing in signal/imaging processing. Two critical dimensions of the stability region, that is, maximal intervals along the imaginary and negative real axes, are employed as the criteria for stability optimization. This gives the largest Courant–Friedrichs–Lewy time steps in solving hyperbolic and parabolic partial differential equations, respectively. Numerical experiments are conducted to validate the optimized time‐stepping schemes. Copyright © 2013 John Wiley & Sons, Ltd.     

An adaptive wavelet viscosity method for hyperbolic conservation laws

We extend the multiscale finite element viscosity method for hyperbolic conservation laws developed in terms of hierarchical finite element bases to a (pre‐orthogonal spline‐)wavelet basis. Depending on an appropriate error criterion, the multiscale framework allows for a controlled adaptive resolution of discontinuities of the solution. The nonlinearity in the weak form is treated by solving a least‐squares data fitting problem. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2008     

Proof interpretations with truth

This article systematically investigates so‐called “truth variants” of several functional interpretations. We start by showing a close relation between two variants of modified realizability, namely modified realizability with truth and q‐modified realizability. Both variants are shown tobe derived from a single “functional interpretation with truth” of intuitionistic linear logic. This analysis suggests that several functional interpretations have truth and q‐variants. These variants, however, require a more involved modification than the ones previously considered. Following this lead we present truth and q‐variants of the Diller‐Nahm interpretation, the bounded modified realizability and the bounded functional interpretation (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A nonconventional Eulerian‐Lagrangian single‐node collocation method with Hermite polynomials for unsteady‐state advection‐diffusion equations

We developed a nonconventional Eulerian‐Lagrangian single‐node collocation method (ELSCM) with piecewise‐cubic Hermite polynomials as basis functions for the numerical simulation to unsteady‐state advection‐diffusion transport partial differential equations. This method greatly reduces the number of unknowns in the conventional collocation method, and generates accurate numerical solutions even if very large time steps are taken. The method is relatively easy to formulate. Numerical experiments are presented to show the strong potential of this method. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 271–283, 2003.     

A variant of the IDR(s) method with the quasi-minimal residual strategy

The IDR($s$) method proposed by Sonneveld and van Gijzen is an effective method for solving nonsymmetric linear systems, but usually with irregular convergence behavior. In this paper, we reformulate the relations of residuals and their auxiliary vectors generated by the IDR($s$) method in matrix form. Then, using this new formulation and motivated by other QMR-type methods, we propose a variant of the IDR($s$) method, called QMRIDR($s$), for overcoming the disadvantage of its irregular convergence behavior. Both fast and smooth convergence behaviors of the QMRIDR($s$) method can be shown. Numerical experiments are reported to show the efficiency of our proposed method.     

A note on simultaneous preconditioning and symmetrization of non‐symmetric linear systems

Motivated by the theory of self‐duality that provides a variational formulation and resolution for non‐self‐adjoint partial differential equations (Ann. Inst. Henri Poincaré (C) Anal Non Linéaire 2007; 24 :171–205; Selfdual Partial Differential Systems and Their Variational Principles. Springer: New York, 2008), we propose new templates for solving large non‐symmetric linear systems. The method consists of combining a new scheme that simultaneously preconditions and symmetrizes the problem, with various well‐known iterative methods for solving linear and symmetric problems. The approach seems to be efficient when dealing with certain ill‐conditioned, and highly non‐symmetric systems. The numerical and theoretical results are provided to show the efficiency of our approach. Copyright © 2010 John Wiley & Sons, Ltd.     

An explicit spectral collocation method using nonpolynomial basis functions for the time‐dependent Schrödinger equation

We propose a spectral collocation method for the numerical solution of the time‐dependent Schrödinger equation, where the newly developed nonpolynomial functions in a previous study are used as basis functions. Equipped with the new basis functions, various boundary conditions can be imposed exactly. The preferable semi‐implicit time marching schemes are employed for temporal discretization. Moreover, the new basis functions build in a free parameter λ intrinsically, which can be chosen properly so that the semi‐implicit scheme collapses to an explicit scheme. The method is further applied to linear Schrödinger equation set in unbounded domain. The transparent boundary conditions are constructed for time semidiscrete scheme of the linear Schrödinger equation. We employ spectral collocation method using the new basis functions for the spatial discretization, which allows for the exact imposition of the transparent boundary conditions. Comprehensive numerical tests both in bounded and unbounded domain are performed to demonstrate the attractive features of the proposed method.     

Parameters Related to Tree‐Width,Zero Forcing,and Maximum Nullity of a Graph

Tree‐width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree‐width, largeur d'arborescence, path‐width, and proper path‐width are each characterized in terms of a minor monotone floor of a certain zero forcing parameter defined by a color change rule.     

Preconditioner updates for solving sequences of linear systems in matrix‐free environment

We present two new ways of preconditioning sequences of nonsymmetric linear systems in the special case where the implementation is matrix free. Both approaches are fully algebraic, they are based on the general updates of incomplete LU decompositions recently introduced in (SIAM J. Sci. Comput. 2007; 29 (5):1918–1941), and they may be directly embedded into nonlinear algebraic solvers. The first of the approaches uses a new model of partial matrix estimation to compute the updates. The second approach exploits separability of function components to apply the updated factorized preconditioner via function evaluations with the discretized operator. Experiments with matrix‐free implementations of test problems show that both new techniques offer useful, robust and black‐box solution strategies. In addition, they show that the new techniques are often more efficient in matrix‐free environment than either recomputing the preconditioner from scratch for every linear system of the sequence or than freezing the preconditioner throughout the whole sequence. Copyright © 2010 John Wiley & Sons, Ltd.     

Variational Approaches in the Beam Theory

Equations governing the stress-strain state of an elastic beam are derived on the basis of the method of the integro-differential relations (IDR). The influence of Poisson's ratio and shear modulus on the stiffness characteristics of an elastic beam with a rectangular cross section is investigated. Explicit expressions are obtained for the stress fields in an isotropic or anisotropic beam for an arbitrary type of loading. A system of differential equations for displacement fields in these beams is presented. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parallel Newton two‐stage methods based on ILU factorizations for nonlinear systems

Parallel iterative algorithms based on the Newton method and on two of its variants, the Shamanskii method and the Chord method, for solving nonlinear systems are proposed. These algorithms are based on two‐stage multisplitting methods where incomplete LU factorizations are considered as a mean of constructing the inner splittings. Convergence properties of these parallel methods are studied for H‐matrices. Computational results of these methods on two parallel computing systems are discussed. The reported experiments show the effectiveness of these methods. Copyright © 2006 John Wiley & Sons, Ltd.     

Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.     

Pressure‐based adaption indicator for compressible euler equations

We consider the Euler equations of gas dynamics and develop a new adaption indicator, which is based on the weak local residual measured for the nonconservative pressure variable. We demonstrate that the proposed indicator is capable of automatically detecting discontinuities and distinguishing between the shock and contact waves when they are isolated from each other. We then use the developed indicator to design a scheme adaption algorithm, according to which nonlinear limiters are used only in the vicinity of shocks. The new adaption algorithm is realized using a second‐order limited and a high‐order nonlimited central‐upwind scheme. We demonstrate robustness and high resolution of the designed method on a number of one‐ and two‐dimensional numerical examples. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1844–1874, 2015     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

Solvability of the Goursat problem in quadratures

We find new variants of Goursat problem solution in quadratures on the basis of the combination of the Riemann method and the cascade integration. The results are applied to two Volterra equations with particular integrals.