Search

This paper presents some guidance for choosing multigrid preconditioners for systems of partial differential equations (PDEs). Rather than developing a black-box algorithm for arbitrary systems of PDEs, the strategy in this paper is to classify systems with multigrid preconditioners. From this classification, a new preconditioner is developed, and it is shown to be suitable for a particular class of strongly cross-coupled systems, solving the whole cross-coupled system almost as effectively as solving just the diagonal system. Also, this paper gives an explanation of why block diagonal preconditioners are somewhat effective for certain strongly cross-coupled systems that at first glance appear to be intractable for multigrid preconditioning. [ABSTRACT FROM AUTHOR]

In this paper, we propose iterative algorithms for solving image restoration problems. The iterative algorithms are based on decoupling of deblurring and denoising steps in the restoration process. In the deblurring step, an efficient deblurring method using fast transforms can be employed. In the denoising step, effective methods such as the wavelet shrinkage denoising method or the total variation denoising method can be used. The main advantage of this proposal is that the resulting algorithms can be very efficient and can produce better restored images in visual quality and signalto-noise ratio than those by the restoration methods using the combination of a data-fitting term and a regularization term. The convergence of the proposed algorithms is shown in the paper. Numerical examples are also given to demonstrate the effectiveness of these algorithms. [ABSTRACT FROM AUTHOR]

Dynamical systems can often be decomposed into loosely coupled subsystems. The system of ordinary differential equations (ODEs) modelling such a problem can then be partitioned corresponding to the subsystems, and the loose couplings can be exploited by special integration methods to solve the problem using a parallel computer or just solve the problem more efficiently than by standard methods. This paper presents accuracy analysis of methods for the numerical integration of stiff partitioned systems of ODEs. The discretization formulas are based on the implicit Euler formula and the second order implicit backward differentiation formula (BDF2). Each subsystem of the partitioned problem is discretized independently, and the couplings to the other subsystems are based on solution values from previous time steps. Applied this way, the discretization formulas are called decoupled. The stability properties of the decoupled implicit Euler formula are well understood. This paper presents error bounds and asymptotic error expansions to be used in controlling step size, relaxation between subsystems and the validity of the partitioning. The decoupled BDF2 formula is analyzed within the same framework. Finally, the analysis is used in the design of a decoupled numerical integration algorithm with variable step size to control the local error and adaptive selection of partitionings. Two versions of the algorithm with decoupled implicit Euler and BDF2, respectively, are used in examples where a realistic problem is solved. The examples compare the results from the decoupled implicit Euler and BDF2 formulas, and compare them with results from the corresponding classical formulas. [ABSTRACT FROM AUTHOR]

This paper analyzes the process of merging groups of many Gaussian basis functions into a single basis function in vortex simulations. Analysis of the equations governing this process yields fundamental parameters and uniform estimates of the merger-induced error. In a merging event, the uniform error bound depends only on relationships between nearby computational elements permitting fast and effective merging schemes. In this paper, one such algorithm is proposed and demonstrated. [ABSTRACT FROM AUTHOR]

In this paper, we consider the unilateral frictional contact problem of a hyperelastic body in the case of large displacements and small strains. In order to retain the linear elasticity framework, we decompose the deformation into a large global rotation and a small elastic displacement. This corotational approach is combined with a primal-dual active set strategy to tackle the contact problem. The resulting algorithm preserves both energy and angular momentum. [ABSTRACT FROM AUTHOR]

In this paper we present a new incomplete factorization of a square matrix into triangular factors in which we get standard LU or LDLT factors (direct factors) and their inverses (inverse factors) at the same time. Algorithmically, we derive this method from the approach based on the Sherman-Morrison formula [R. Bru, J. Cerdán, J. Marín, and J. Mas, SIAM J. Sci. Comput., 25 (2003), pp. 701-715]. In contrast to the robust incomplete decomposition (RIF) algorithm [M. Benzi and M. Tůma, Numer. Linear Algebra Appl., 10 (2003), pp. 385-400] the direct and inverse factors here directly influence each other throughout the computation. Consequently, the algorithm to compute the approximate factors may mutually balance dropping in the factors and control their conditioning in this way. For the symmetric positive definite case, we derive the theory and present an algorithm for computing the incomplete LDLT factorization, and we discuss experimental results. We call this new approximate LDLT factorization the balanced incomplete factorization (BIF). Our experimental results confirm that this factorization is very robust and may be useful in solving difficult ill conditioned problems by preconditioned iterative methods. Moreover, the internal coupling of the computation of direct and inverse factors results in much shorter setup times (times to compute approximate decomposition) than RIF, a method of a similar and very high level of robustness. We also derive and present the theory for the general nonsymmetric case, but do not discuss its implementation. [ABSTRACT FROM AUTHOR]

We describe an asynchronous parallel derivative-free algorithm for linearly constrained optimization. Generating set search (GSS) is the basis of our method. At each iteration, a GSS algorithm computes a set of search directions and corresponding trial points and then evaluates the objective function value at each trial point. Asynchronous versions of the algorithm have been developed in the unconstrained and bound-constrained cases which allow the iterations to continue (and new trial points to be generated and evaluated) as soon as any other trial point completes. This enables better utilization of parallel resources and a reduction in overall run time, especially for problems where the objective function takes minutes or hours to compute. For linearly constrained GSS, the convergence theory requires that the set of search directions conforms to the nearby boundary. This creates an immediate obstacle for asynchronous methods where the definition of nearby is not well defined. In this paper, we develop an asynchronous linearly constrained GSS method that overcomes this difficulty and maintains the original convergence theory. We describe our implementation in detail, including how to avoid function evaluations by caching function values and using approximate lookups. We test our implementation on every CUTEr test problem with general linear constraints and up to 1000 variables. Without tuning to individual problems, our implementation was able to solve 95% of the test problems with 10 or fewer variables, 73% of the problems with 11-100 variables, and nearly half of the problems with 100-1000 variables. To the best of our knowledge, these are the best results that have ever been achieved with a derivative-free method for linearly constrained optimization. Our asynchronous parallel implementation is freely available as part of the APPSPACK software. [ABSTRACT FROM AUTHOR]

We discuss in this paper the numerical approximation of fluid-structure interaction (FSI) problems dealing with strong added-mass effect. We propose new semi-implicit algorithms based on inexact block-LU factorization of the linear system obtained after the space-time discretization and linearization of the FSI problem. As a result, the fluid velocity is computed separately from the coupled pressure-structure velocity system at each iteration, reducing the computational cost. We investigate explicit-implicit decomposition through algebraic splitting techniques originally designed for the FSI problem. This approach leads to two different families of methods which extend to FSI the algebraic pressure correction method and the Yosida method, two schemes that were previously adopted for pure fluid problems. Furthermore, we have considered the inexact factorization of the fluid-structure system as a preconditioner. The numerical properties of these methods have been tested on a model problem representing a blood-vessel system. [ABSTRACT FROM AUTHOR]

In this paper we describe a simple algorithm for the approximation of an invariant curve T of a planar map f. We are particularly interested in the case where T is attracting but not smooth. Results for the delayed logistic map illustrate the performance of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we present a new ILU decomposition which is based on an existing sparse direct solver. In contrast to many incomplete LU decompositions this ILU incorporates information about the inverse factors L-1 and U-1 which have direct influence on the dropping strategy. We demonstrate in several large scale examples that this implementation constructs a robust preconditioner. [ABSTRACT FROM AUTHOR]

In this paper, a discrete singular convolution (DSC) algorithm is introduced to solve Fisher’s equation, to which obtaining an accurate and reliable traveling wave solution is a challenging numerical problem. Two novel numerical treatments, a moving frame scheme and a new asymptotic scheme, are designed to overcome the subtle difficulties involved in the numerical solution of Fisher’s equation. The moving frame scheme is proposed to provide accurate and efficient spatial resolution of the problem. The new asymptotic scheme is introduced to facilitate the correct prediction of the wave speed after long-time integrations. The resulting DSC algorithm is able to correctly predict long-time traveling wave behavior. The performance of the present algorithm is demonstrated through extensive numerical experiments as well as through a comparison with three other standard approaches, i.e., methods of the Fourier pseudospectral, the accurate spatial derivatives, and the Crank­Nicolson schemes. The spatial and temporal accuracies of all four methods are analyzed and numerically verified. [ABSTRACT FROM AUTHOR]

The Schwarz alternating method can be used to solve linear elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approx- imated by an infinite sequence of functions which result from solving a sequence of elliptic boundary value problems in each of the subdomains. This paper considers four Schwarz alternating methods for the N-dimensional, steady, viscous, incompressible Navier­Stokes equations, N ≤ 4. It is shown that the Schwarz sequences converge to the true solution provided that the Reynolds number is sufficiently small. [ABSTRACT FROM AUTHOR]

In this paper, we study some efficient numerical methods for parameter identifications in elliptic systems. The proposed numerical methods are conducted iteratively and each iteration involves only solving positive definite linear algebraic systems, although the original inverse problems are ill-posed and highly nonlinear. The positive definite systems can be naturally preconditioned with their corresponding block diagonal matrices. Numerical experiments are presented to illustrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The use of approximate projection methods for modeling low Mach number flows avoids many of the numerical complications associated with exact projection methods, but introduces additional design choices in developing a robust algorithm. In this paper we first explore these design choices in the setting of inviscid incompressible flow using several computational examples. We then develop a framework for analyzing the behavior of the different design variations and use that analysis to explain the features observed in the computations. As part of this work we introduce a new variation of the approximate projection algorithm that combines the advantages of several of the previous versions. [ABSTRACT FROM AUTHOR]

This paper presents the results of a scalability study for a three-dimensional semi- coarsening multigrid solver on a distributed memory computer. In particular, we are interested in the scalability of the solver-how the solution time varies as both problem size and number of processors are increased. For an iterative linear solver, scalability involves both algorithmic issues and implementation issues. We examine the scalability of the solver theoretically by constructing a simple parallel model and experimentally by results obtained on an IBM SP. The results are compared with those obtained for other solvers on the same computer. [ABSTRACT FROM AUTHOR]

In this paper we consider a matrix-free path following algorithm for nonlinear parameter-dependent compact fixed point problems. We show that if these problems are discretized so that certain collective compactness and strong convergence properties hold, then this algorithm can follow smooth folds and capture simple bifurcations in a mesh-independent way. [ABSTRACT FROM AUTHOR]

Multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan­Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of-the-art partitioner and shown to provide improved results. [ABSTRACT FROM AUTHOR]

A successive continuation method for locating connecting orbits in parametrized systems of autonomous ODEs was considered in [Numer. Algorithms, 14 (1997), pp. 103­124]. In this paper we present an improved algorithm for locating and continuing connecting orbits, which includes a new algorithm for the continuation of invariant subspaces. The latter algorithm is of independent interest and can be used in contexts different than the present one. [ABSTRACT FROM AUTHOR]

Low-rank approximation of large and/or sparse matrices is important in many applications, and the singular value decomposition (SVD) gives the best low-rank approximations with respect to unitarily-invariant norms. In this paper we show that good low-rank approximations can be directly obtained from the Lanczos bidiagonalization process applied to the given matrix without computing any SVD. We also demonstrate that a so-called one-sided reorthogonalization process can be used to maintain an adequate level of orthogonality among the Lanczos vectors and produce accurate low-rank approximations. This technique reduces the computational cost of the Lanczos bidiagonalization process. We illustrate the efficiency and applicability of our algorithm using numerical examples from several applications areas. [ABSTRACT FROM AUTHOR]

Multidimensional positive definite advection transport algorithm (MPDATA) is an iterative process for approximating the advection equation, which uses a donor cell approximation to compensate for the truncation error of the originally specified donor cell scheme. This step may be repeated an arbitrary number of times, leading to successively more accurate solutions to the advection equation. In this paper, we show how to sum the successive approximations analytically to find a single antidiffusive velocity that represents the effects of an arbitrary number of passes. The analysis is first done in one dimension to illustrate the method and then is repeated in two dimensions. The existence of cross terms in the truncation analysis of the two-dimensional equations introduces an extra complication into the calculation. We discuss the implementation of our new antidiffusive velocities and provide some examples of applications, including a third-order accurate scheme. [ABSTRACT FROM AUTHOR]

In this paper we present several new fast and reliable algorithms for solving rank-deficient linear least squares problems by means of the complete orthogonal decomposition. Experimental comparison of our algorithms with the existing implementations in LAPACK on a wide range of platforms shows considerable performance improvements. Moreover, for full-rank matrices the performance of the new algorithm is very close to that of the fast method based on QR factorization, thus providing a valuable general tool for full-rank matrices, rank-deficient matrices, and those matrices with unknown rank. [ABSTRACT FROM AUTHOR]

In this paper we describe and analyze a class of nonlinear multiresolution schemes for the multiresolution setting which corresponds to discretization by local averages with respect to the hat function. These schemes are based on the essentially-non-oscillatory (ENO) interpolatory procedure described in [A. Harten, B. Engquist, S. Osher, and S. Chakravarthy, J. Comput. Phys., 71 (1987), pp. 231–302]. We show that by allowing the approximation to fit the local nature of the data, one can improve the compression capabilities of the multiresolution algorithms. The question of stability for nonlinear (data-dependent) reconstruction techniques is also addressed. [ABSTRACT FROM AUTHOR]

When performing sparse matrix factorization, the ordering of matrix rows and columns has a dramatic impact on the factorization time. This paper describes an approach to the reordering problem that produces significantly better orderings than prior methods. The algorithm is a hybrid of nested dissection and minimum degree ordering, and combines an assortment of different algorithmic advances. New or improved algorithms are described for graph compression, multilevel partitioning, and separator improvement. When these techniques are combined, the resulting orderings average 39% better than minimum degree over a suite of test matrices, while requiring roughly 2.7 times the run time of Liu's multiple minimum degree. [ABSTRACT FROM AUTHOR]