Mathematical modeling and numerical simulation of telephone cord buckles of elastic films

An annular sector model for the telephone cord buckles of elastic thin films on rigid substrates is established, in which the von Krman plate equations in polar coordinates are used for the elastic thin film and a discrete version of the Griffith criterion is applied to determine the shape and scale of the parameters. A numerical algorithm combining the Newmark-β scheme and the Chebyshev collocation method is designed to numerically solve the problem in a quasi-dynamic process. Numerical results are presen...     

ACCELERATION METHODS OF NONLINEAR ITERATION FOR NONLINEAR PARABOLIC EQUATIONS

This paper discusses the accelerating of nonlinear parabolic equations. Two iterative methods for solving the implicit scheme new nonlinear iterative methods named by the implicit-explicit quasi-Newton （IEQN） method and the derivative free implicit-explicit quasi-Newton （DFIEQN） method are introduced, in which the resulting linear equations from the linearization can preserve the parabolic characteristics of the original partial differential equations. It is proved that the iterative sequence of the iteration method can converge to the solution of the implicit scheme quadratically. Moreover, compared with the Jacobian Free Newton-Krylov （JFNK） method, the DFIEQN method has some advantages, e.g., its implementation is easy, and it gives a linear algebraic system with an explicit coefficient matrix, so that the linear （inner） iteration is not restricted to the Krylov method. Computational results by the IEQN, DFIEQN, JFNK and Picard iteration methods are presented in confirmation of the theory and comparison of the performance of these methods.     

A GENERAL DETERMINISTIC PIVOT METHOD FOR ORIENTED MATROID PROGRAMMING

A new pivot method for oriented matroid progiamming is given out. This mathod is deterministic by nature and is general in the sense that its flexible pivot selection rule allows a family of possible algorithms to be its special cases, including the so called criss-cross algorithm and the Edmonds-Fukuda algorithm as well. As an example of a special implementation of our general method, an extended version of the Edmonds-Fukuda algorithm is presented.     

MODIFIED BERNOULLI ITERATION METHODS FOR QUADRATIC MATRIX EQUATION

We construct a modified Bernoulli iteration method for solving the quadratic matrix equation AX^2 ＋ BX ＋ C = 0, where A, B and C are square matrices. This method is motivated from the Gauss-Seidel iteration for solving linear systems and the ShermanMorrison-Woodbury formula for updating matrices. Under suitable conditions, we prove the local linear convergence of the new method. An algorithm is presented to find the solution of the quadratic matrix equation and some numerical results are given to show the feasibility and the effectiveness of the algorithm. In addition, we also describe and analyze the block version of the modified Bernoulli iteration method.     

The computation of Buehler confidence limits

In medicine and industry, small sample size often arises owing to the high test cost. Then exact confidence inference is important. Buehler confidence limit is a kind of exact confidence limit for the function of parameters in a model. It can be always defined if the order in sample space is given. But the computing problem is often difficult, especially for the cases with high dimension parameter or with incomplete data. This paper presents an algorithm to compute the Buehler confidence limits by EM algorithm. This is the first-time usage of EM algorithm on Buehler confidence limits, but the algorithm is often used for maximum likelihood estimate in literatures. Three computation examples are given to illustrate the method.     

MULTIGRID METHOD FOR A MODIFIED CURVATURE DRIVEN DIFFUSION MODEL FOR IMAGE INPAINTING

Digital inpainting is a fundamental problem in image processing and many variational models for this problem have appeared recently in the literature. Among them are the very successfully Total Variation （TV） model [11] designed for local inpainting and its improved version for large scale inpainting： the Curvature-Driven Diffusion （CDD） model [10]. For the above two models, their associated Euler Lagrange equations are highly nonlinear partial differential equations. For the TV model there exists a relatively fast and easy to implement fixed point method, so adapting the multigrid method of [24] to here is immediate. For the CDD model however, so far only the well known but usually very slow explicit time marching method has been reported and we explain why the implementation of a fixed point method for the CDD model is not straightforward. Consequently the multigrid method as in [Savage and Chen, Int. J. Comput. Math., 82 （2005）, pp. 1001-1015] will not work here. This fact represents a strong limitation to the range of applications of this model since usually fast solutions are expected. In this paper, we introduce a modification designed to enable a fixed point method to work and to preserve the features of the original CDD model. As a result, a fast and efficient multigrid method is developed for the modified model. Numerical experiments are presented to show the very good performance of the fast algorithm.     

MODIFIED LEAST SQUARE METHOD ON COMPUTING DIRICHLET PROBLEMS

The singularity theory of dynamical systems is linked to the numerical computation of boundary value problems of differential equations. It turns out to be a modified least square method for a calculation of variational problem defined on Ck(Ω), in which the base functions are polynomials and the computation of problems is transferred to compute the coefficients of the base functions. The theoretical treatment and some simple examples are provided for understanding the modification procedure of the methods. A modified least square method on difference scheme is introduced with a general matrix form of dynamical systems. We emphasize the simplicity of the algorithm and only use Euler algorithm to compute initial value problems of ODEs. A better algorithm is needed to reduce the stiffness of ODEs.     

ACCURATE ATTENUATION CORRECTION FOR ALGEBRAIC RECONSTRUCTION TECHNIQUE IN SPECT

We present a new iterative reconstruction algorithm to improve the algebraic reconstruction technique （ART） for the Single-Photon Emission Computed Tomography. Our method is a generalization of the Kaczmarz iterative algorithm for solving linear systems of equations and introduces exact and implicit attenuation correction derived from the attenuated Radon transform operator at each step of the algorithm. The performances of the presented algorithm have been tested upon various numerical experiments in presence of both strongly non-uniform attenuation and incomplete measurements data. We also tested the ability of our algorithm to handle moderate noisy data. Simulation studies demonstrate that the proposed method has a significant improvement in the quality of reconstructed images over ART. Moreover, convergence speed was improved and stability was established, facing noisy data, once we incorporate filtration procedure in our algorithm.     

A note on a generalized network flow model for manufacturing process

Manufacturing network flow （MNF） is a generalized network model that overcomes the limitation of an ordinary network flow in modeling more complicated manufacturing scenarios, in particular the synthesis of different materials into one product and/or the distilling of one type of material into many different products. Though a network simplex method for solving a simplified version of MNF has been outlined in the literature, more research work is still needed to give a complete answer whether some classical duality and optimality results of the classical network flow problem can be extended in MNF. In this paper, we propose an algorithmic method for obtaining an initial basic feasible solution to start the existing network simplex algorithm, and present a network-based approach to checking the dual feasibility conditions. These results are an extension of those of the ordinary network flow problem.     

A superlinearly and quadratically convergent SQP type feasible method for constrained optimization

A new SQP type feasible method for inequality constrained optimization is presented, it is a combination of a master algorithm and an auxiliary algorithm which is taken only in finite iterations. The directions of the master algorithm are generated by only one quadratic programming, and its step-size is always one, the directions of the auxiliary algorithm are new “secondorder“ feasible descent. Under suitable assumptions, the algorithm is proved to possess global and strong convergence, superlinear and quadratic convergence.     

On IGMRES: An incomplete generalized minimal residual method for large unsymmetric linear systems

The truncated version of the generalized minimal residual method (GMRES), the incomplete generalized minimal residual method (IGMRES), is studied. It is based on an incomplete orthogonalization of the Krylov vectors in question, and gives an approximate or quasi-minimum residual solution over the Krylov subspace. A convergence analysis of this method is given, showing that in the non-restarted version IGMRES can behave like GMRES once the basis vectors of Krylov subspace generated by the incomplete orthogonalization are strongly linearly independent. Meanwhile, some relationships between the residual norms for IOM and IGMRES are established. Numerical experiments are reported to show convergence behavior of IGMRES and of its restarted version IGMRES(m). Project supported by the China State Key Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Returning Scholars of China and the Natural Science Foundation of Liaoning Province.     

DQGMRES: a Direct Quasi-minimal Residual Algorithm Based on Incomplete Orthogonalization

We describe a Krylov subspace technique, based on incomplete orthogonalization of the Krylov vectors, which can be considered as a truncated version of GMRES. Unlike GMRES(m), the restarted version of GMRES, the new method does not require restarting. Like GMRES, it does not break down. Numerical experiments show that DQGMRES(k) often performs as well as the restarted GMRES using a subspace of dimension m=2k. In addition, the algorithm is flexible to variable preconditioning, i.e., it can accommodate variations in the preconditioner at every step. In particular, this feature allows the use of any iterative solver as a right-preconditioner for DQGMRES(k). This inner-outer iterative combination often results in a robust approach for solving indefinite non-Hermitian linear systems.     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

Block Krylov–Schur method for large symmetric eigenvalue problems

Stewart’s Krylov–Schur algorithm offers two advantages over Sorensen’s implicitly restarted Arnoldi (IRA) algorithm. The first is ease of deflation of converged Ritz vectors, the second is the avoidance of the potential forward instability of the QR algorithm. In this paper we develop a block version of the Krylov–Schur algorithm for symmetric eigenproblems. Details of this block algorithm are discussed, including how to handle rank deficient cases and how to use varying block sizes. Numerical results on the efficiency of the block Krylov–Schur method are reported.     

Hybrid enriched bidiagonalization for discrete ill‐posed problems

The regularizing properties of the Golub–Kahan bidiagonalization algorithm are powerful when the associated Krylov subspace captures the dominating components of the solution. In some applications the regularized solution can be further improved by enrichment, that is, by augmenting the Krylov subspace with a low‐dimensional subspace that represents specific prior information. Inspired by earlier work on GMRES, we demonstrate how to carry these ideas over to the bidiagonalization algorithm, and we describe how to incorporate Tikhonov regularization. This leads to a hybrid iterative method where the choice of regularization parameter in each iteration also provides a stopping rule.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

Krylov subspace methods with deflation and balancing preconditioners for least squares problems

For solving least squares problems, the CGLS method is a typical method in the point of view of iterative methods. When the least squares problems are ill-conditioned, the convergence behavior of the CGLS method will present a deteriorated result. We expect to select other iterative Krylov subspace methods to overcome the disadvantage of CGLS. Here the GMRES method is a suitable algorithm for the reason that it is derived from the minimal residual norm approach, which coincides with least squares problems. Ken Hayami proposed BAGMRES for solving least squares problems in [\emph{GMRES Methods for Least Squares Problems, SIAM J. Matrix Anal. Appl., 31(2010)}, pp.2400-2430]. The deflation and balancing preconditioners can optimize the convergence rate through modulating spectral distribution. Hence, in this paper we utilize preconditioned iterative Krylov subspace methods with deflation and balancing preconditioners in order to solve ill-conditioned least squares problems. Numerical experiments show that the methods proposed in this paper are better than the CGLS method.     

An extension of the conjugate residual method to nonsymmetric linear systems

The Conjugate Gradient (CG) method and the Conjugate Residual (CR) method are Krylov subspace methods for solving symmetric (positive definite) linear systems. To solve nonsymmetric linear systems, the Bi-Conjugate Gradient (Bi-CG) method has been proposed as an extension of CG. Bi-CG has attractive short-term recurrences, and it is the basis for the successful variants such as Bi-CGSTAB. In this paper, we extend CR to nonsymmetric linear systems with the aim of finding an alternative basic solver. Numerical experiments show that the resulting algorithm with short-term recurrences often gives smoother convergence behavior than Bi-CG. Hence, it may take the place of Bi-CG for the successful variants.     

On the convergence of two‐level Krylov methods for singular symmetric systems

We discuss the convergence of a two‐level version of the multilevel Krylov method for solving linear systems of equations with symmetric positive semidefinite matrix of coefficients. The analysis is based on the convergence result of Brown and Walker for the Generalized Minimal Residual method (GMRES), with the left‐ and right‐preconditioning implementation of the method. Numerical results based on diffusion problems are presented to show the convergence.     

On the Vector ε-Algorithm for Solving Linear Systems of Equations

The four vector extrapolation methods, minimal polynomial extrapolation, reduced rank extrapolation, modified minimal polynomial extrapolation and the topological epsilon algorithm, when applied to linearly generated vector sequences are Krylov subspace methods and it is known that they are equivalent to some well-known conjugate gradient type methods. However, the vector -algorithm is an extrapolation method, older than the four extrapolation methods above, and no similar results are known for it. In this paper, a determinantal formula for the vector -algorithm is given. Then it is shown that, when applied to a linearly generated vector sequence, the algorithm is also a Krylov subspace method and for a class of matrices the method is equivalent to a preconditioned Lanczos method. A new determinantal formula for the CGS is given, and an algebraic comparison between the vector -algorithm for linear systems and CGS is also given.