Search

As a solution to the frequently reported problem of the high frequencies reconstructed sometimes many iterations after the low frequencies in tomography, we proposed in a recent paper [V. Israel-Jost, Ph. Choquet, and A. Constantinesco, Int. J. Biomed. Imaging, 2006, paper 34043.] a general adaptation that can apply to many algorithms: the incomplete backprojection. We stressed the fact that this type of frequency adapted (FA) algorithm works only when the linear problem of tomography to be solved involves deblurring, i.e., when the point spread functions (PSFs) associated with each voxel are large. Thus, depending on the desired level of detail, a parameter is set to achieve the reconstruction within a small number of iterations. The aim of this paper is to give a mathematical analysis of both the acceleration obtained and the convergence of an FA algorithm derived from the simultaneous algebraic reconstruction technique (SART) algorithm of Andersen and Kak, the so-called FA-SART algorithm. [ABSTRACT FROM AUTHOR]

This paper is concerned with the numerical simulations for the dynamics of the molecular beam epitaxy (MBE) model. The numerical simulations of the MBE models require long time computations, and therefore large time-stepping methods become necessary. In this work, we consider some unconditionally energy stable finite difference schemes, which will be used in the time adaptivity strategies. It is found that the use of the time adaptivity cannot only resolve the steady-state solutions but also the dynamical changes of the solution accurately and efficiently. The adaptive time step is selected based on the energy variation or the change of the roughness of the solution. The numerical experiments demonstrated that the CPU time is significantly saved for long time simulations. [ABSTRACT FROM AUTHOR]

We develop in this paper some efficient algorithms which are essential to implementations of spectral methods on the sparse grid by Smolyak's construction based on a nested quadrature. More precisely, we develop a fast algorithm for the discrete transform between the values at the sparse grid and the coefficients of expansion in a hierarchical basis; and by using the aforementioned fast transform, we construct two very efficient sparse spectral-Galerkin methods for a model elliptic equation. In particular, the Chebyshev Legendre-Galerkin method leads to a sparse matrix with a much lower number of nonzero elements than that of low-order sparse grid methods based on finite elements or wavelets, and can be efficiently solved by a suitable sparse solver. Ample numerical results are presented to demonstrate the efficiency and accuracy of our algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present optimization algorithms for image restoration based on the total variation (TV) minimization framework of Rudin, Osher, and Fatemi (ROF). Our approach formulates TV minimization as a second-order cone program which is then solved by interior-point algorithms that are efficient both in practice (using nested dissection and domain decomposition) and in theory (i.e., they obtain solutions in polynomial time). In addition to the original ROF minimization model, we show how to apply our approach to other TV models, including ones that are not solvable by PDE-based methods. Numerical results on a varied set of images are presented to illustrate the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

This paper formulates several algorithms for the direct computation of periodic orbits as solutions of boundary value problems. The algorithms emphasize the use of coarse meshes and high orders of accuracy. Convergence theorems are given in the limit of increasing order with a fixed mesh. The algorithms are implemented with the use of MATLAB and ADOL-C, a software package for automatic differentiation. Automatic differentiation enables accurate computation of high-order derivatives of functions without the truncation errors inherent in finite difference calculations. We embed the algorithms in a continuation framework and extend them to compute saddle-node bifur- cations of periodic orbits directly. We present data from numerical studies of four test problems, making some comparisons with other methods for computing periodic orbits. These results demonstrate that high-order methods based upon automatic differentiation are capable of high precision with small meshes. [ABSTRACT FROM AUTHOR]

We study parallel two-level overlapping Schwarz algorithms for solving nonlinear finite element problems, in particular, for the full potential equation of aerodynamics discretized in two dimensions with bilinear elements. The overall algorithm, Newton-Krylov-Schwarz (NKS), employs an inexact finite difference Newton method and a Krylov space iterative method, with a two-level overlapping Schwarz method as a preconditioner. We demonstrate that NKS, combined with a density upwinding continuation strategy for problems with weak shocks, is robust and economical for this class of mixed elliptic-hyperbolic nonlinear partial differential equations, with proper specification of several parameters. We study upwinding parameters, inner convergence tolerance, coarse grid density, subdomain overlap, and the level of fill-in in the incomplete factorization, and report their effect on numerical convergence rate, overall execution time, and parallel efficiency on a distributed-memory parallel computer. [ABSTRACT FROM AUTHOR]

We present a novel algorithm for tetrahedral image-to-mesh conversion which allows for guaranteed bounds on the smallest dihedral angle and on the distance between the boundaries of the mesh and the boundaries of the tissues. The algorithm produces a small number of mesh elements that comply with these bounds. We also describe and evaluate our implementation of the proposed algorithm that is compatible in performance with a state-of-the art Delaunay code, but in addition solves the small dihedral angle problem. [ABSTRACT FROM AUTHOR]

A FETI-DP (dual-primal finite element tearing and interconnecting) algorithm for the three-dimensional Stokes problem is developed and analyzed. This is an extension of the previous work for the two-dimensional problem in [H. H. Kim, C.-O. Lee, and E.-H. Park, SIAM J. Numer. Anal., 47 (2010), pp. 4142-4162]. Advantages of this approach are the coarse problem without primal pressure unknowns and the use of a computationally cheap lumped preconditioner. Especially ill three dimensions, these advantages provide a more practical FETI-DP algorithm. Ill three dimensions, the velocity unknowns at subdomain corners and the averages of velocity unknowns over common faces are selected as the primal unknowns in the FETI-DP formulation. Its condition number bound is analyzed to be CH/h, where C is a positive constant which is independent of any mesh parameters and H/h is the number of elements across each subdomain. Numerical results are included. [ABSTRACT FROM AUTHOR]

The increasing gap between processor performance and memory access time warrants the re-examination of data movement in iterative linear solver algorithms. For this reason, we explore and establish the feasibility of modifying a standard iterative linear solver algorithm in a manner that reduces the movement of data through memory. In particular, we present an alternative to the restarted GMRES algorithm for solving a single right-hand side linear system Ax = b based on solving the block linear system AX = B. Algorithm performance, i.e., time to solution, is improved by using the matrix A in operations on groups of vectors. Experimental results demonstrate the importance of implementation choices on data movement as well as the effectiveness of the new method on a variety of problems from different application areas. [ABSTRACT FROM AUTHOR]

We describe algorithms used in our construction of a fourth-order in time evolution for the full Einstein equations and assess the accuracy of some representative solutions. The scheme employs several novel geometric and numerical techniques, including a geometrically invariant co- ordinate gauge, which leads to a characteristic-transport formulation of the underlying hyperbolic system, combined with a ‘method of lines’ evolution; convolution splines for radial interpolation, regridding, differentiation, and noise suppression; representations using spin-weighted spherical har- monics; and a spectral preconditioner for solving a class of first-order elliptic systems on S2. Initial data for the evolution is unconstrained, subject only to a mild size condition. For sample initial data of ‘intermediate’ strength (19% of the total mass in gravitational energy), the code is accurate to 1 part in 105, until null time z = 55m when the coordinate condition breaks down. [ABSTRACT FROM AUTHOR]