Hierarchical-matrix method for a class of diffusion-dominated partial integro-differential equations

A hierarchical matrix approach for solving diffusion-dominated partial integro-differential problems is presented. The corresponding diffusion-dominated differential operator is discretized by a second-order accurate finite-volume scheme, while the Fredholm integral term is approximated by the trapezoidal rule. The hierarchical matrix approach is used to approximate the resulting algebraic problem and includes the implementation of an efficient preconditioned generalized minimum residue (GMRes) solver. This approach extends previous work on integral forms of boundary element methods by taking into account inherent characteristics of the diffusion-dominated differential operator in the resultant algebraic problem. Numerical analysis estimates of the accuracy and stability of the finite-volume and the trapezoidal rule approximation are presented and combined with estimates of the hierarchical-matrix approximation and with the accuracy of the GMRes iterates. Results of numerical experiments are reported that successfully validate the theoretical accuracy and convergence estimates, and demonstrate the almost optimal computational complexity of the proposed solution procedure.     

L-Curve and Curvature Bounds for Tikhonov Regularization

The L-curve is a popular aid for determining a suitable value of the regularization parameter when solving linear discrete ill-posed problems by Tikhonov regularization. However, the computational effort required to determine the L-curve and its curvature can be prohibitive for large-scale problems. Recently, inexpensively computable approximations of the L-curve and its curvature, referred to as the L-ribbon and the curvature-ribbon, respectively, were proposed for the case when the regularization operator is the identity matrix. This note discusses the computation and performance of the L- and curvature-ribbons when the regularization operator is an invertible matrix.     

MULTILEVEL AUGMENTATION METHODS FOR SOLVING OPERATOR EQUATIONS

We introduce multilevel augmentation methods for solving operator equations based on direct sum decompositions of the range space of the operator and the solution space of the operator equation and a matrix splitting scheme. We establish a general setting for the analysis of these methods, showing that the methods yield approximate solutions of the same convergence order as the best approximation from the subspace. These augmentation methods allow us to develop fast, accurate and stable nonconventional numerical algorithms for solving operator equations. In particular, for second kind equations, special splitting techniques are proposed to develop such algorithms. These algorithms are then applied to solve the linear systems resulting from matrix compression schemes using wavelet-like functions for solving Fredholm integral equations of the second kind. For this special case, a complete analysis for computational complexity and convergence order is presented. Numerical examples are included to demonstra     

UPGMA clustering revisited: A weight-driven approach to transitive approximation

A new algorithm is proposed for generating min-transitive approximations of a given similarity matrix (i.e. a symmetric matrix with elements in the unit interval and diagonal elements equal to one). Different approximations are generated depending on the choice of an aggregation operator that plays a central role in the algorithm. If the maximum operator is chosen, then the approximation coincides with the min-transitive closure of the given similarity matrix. In case of the arithmetic mean, a transitive approximation is generated which is, on the average, as close to the given similarity matrix as the approximation generated by the UPGMA hierarchical clustering algorithm. The new algorithm also allows to generate approximations in a purely ordinal setting. As this new approach is weight-driven, the partition tree associated to the corresponding min-transitive approximation can be built layer by layer. Numerical tests carried out on synthetic data are used for comparing different approximations generated by the new algorithm with certain approximations obtained by classical methods.     

Etude statistique des erreurs dans l'arithmetique des ordinateurs; application au controle des resultats d'algorithmes numeriques

Since numerical calculations on a digital computer are performed on operands with a limited number of significant digits it follows that each operator in the computational arithmetic is merely an approximation of the corresponding mathematical operator.Therefore every numerical operation carried out on a computer generates a numerical error.The statistical evaluation of these errors is discussed in the first part of the paper. In the second part, the formulae obtained above are used to assess the validity of numerical results obtained in resolution of linear systems, algebraic equations and in matrix inversion.     

The fast scalar auxiliary variable approach with unconditional energy stability for nonlocal Cahn–Hilliard equation

Comparing with the classical local gradient flow and phase field models, the nonlocal models such as nonlocal Cahn–Hilliard equations equipped with nonlocal diffusion operator can describe more practical phenomena for modeling phase transitions. In this paper, we construct an accurate and efficient scalar auxiliary variable approach for the nonlocal Cahn–Hilliard equation with general nonlinear potential. The first contribution is that we have proved the unconditional energy stability for nonlocal Cahn–Hilliard model and its semi‐discrete schemes carefully and rigorously. Second, what we need to focus on is that the nonlocality of the nonlocal diffusion term will lead the stiffness matrix to be almost full matrix which generates huge computational work and memory requirement. For spatial discretizaion by finite difference method, we find that the discretizaition for nonlocal operator will lead to a block‐Toeplitz–Toeplitz‐block matrix by applying four transformation operators. Based on this special structure, we present a fast procedure to reduce the computational work and memory requirement. Finally, several numerical simulations are demonstrated to verify the accuracy and efficiency of our proposed schemes.     

The finite section method and problems in frame theory

The finite section method is a convenient tool for approximation of the inverse of certain operators using finite-dimensional matrix techniques. In this paper we demonstrate that the method is very useful in frame theory: it leads to an efficient approximation of the inverse frame operator and also solves related computational problems in frame theory. In the case of a frame which is localized w.r.t. an orthonormal basis we are able to estimate the rate of approximation. The results are applied to the reproducing kernel frame appearing in the theory for shift-invariant spaces generated by a Riesz basis.     

Factorised Preconditionings of Successive Approximations in Finite Precision

This paper examines the possibility of using the method of successive approximations for the approximate solution of a large system of linear equations with a dense, noncontraction, and ill-conditioned matrix. Using Krasnosel'skii's method of transformation of linear operator equations and functional calculi, the procedure of factorised preconditionings of successive approximations is developed and analysed in the finite precision arithmetic. Numerical results of computational experiments are presented to demonstrate the practicability of the proposed approach.This revised version was published online in October 2005 with corrections to the Cover Date.     

Fast one-sided approximation with spline functions

For the approximation of functions, interpolation compromises approximation error for computational convenience. For a bounded interpolation operator the Lebesque inequality bounds the factor by which the interpolation differs from the best approximation available in the range of the operator. A comparable process for one-sided approximation is not readily apparent. Methods are suggested for the computationally economical construction of one-sided spline approximation to large classes of functions, and criteria for comparing such approximation operators are investigated. Since the operators are generally nonlinear the Lebesque inequality is invalidated as an aid for comparing with the best one-sided approximation in the range of the operator, but comparable inequalities are shown to exist in some cases.     

A note on the iterative solutions of general coupled matrix equation

Recently, Ding and Chen [F. Ding, T. Chen, On iterative solutions of general coupled matrix equations, SIAM J. Control Optim. 44 (2006) 2269-2284] developed a gradient-based iterative method for solving a class of coupled Sylvester matrix equations. The basic idea is to regard the unknown matrices to be solved as parameters of a system to be identified, so that the iterative solutions are obtained by applying hierarchical identification principle. In this note, by considering the coupled Sylvester matrix equation as a linear operator equation we give a natural way to derive this algorithm. We also propose some faster algorithms and present some numerical results.     

二阶算子矩阵代数中的全可导点V

研究二阶算子矩阵代数中的全可导点.利用线性映射与算子矩阵代数运算,以及套代数理论的相关结果,给出并证明了第二行第二列元素为可逆算子,其余元素为零算子的二阶矩阵是二阶算子矩阵代数的关于强算子拓扑的全可导点,推广了相关文献中的结果.     

Iterative representing set selection for nested cross approximation

A new fast algebraic method for obtaining an ‐approximation of a matrix from its entries is presented. The main idea behind the method is based on the nested representation and the maximum volume principle to select submatrices in low‐rank matrices. A special iterative approach for the computation of so‐called representing sets is established. The main advantage of the method is that it uses only the hierarchical partitioning of the matrix and does not require special ‘proxy surfaces’ to be selected in advance. The numerical experiments for the electrostatic problem and for the boundary integral operator confirm the effectiveness and robustness of the approach. The complexity is linear in the matrix size and polynomial in the ranks. The algorithm is implemented as an open‐source Python package that is available online. Copyright © 2015 John Wiley & Sons, Ltd.     

A genetic algorithm for cellular manufacturing design and layout

Cellular manufacturing (CM) is an approach that can be used to enhance both flexibility and efficiency in today’s small-to-medium lot production environment. The design of a CM system (CMS) often involves three major decisions: cell formation, group layout, and group schedule. Ideally, these decisions should be addressed simultaneously in order to obtain the best results. However, due to the complexity and NP-complete nature of each decision and the limitations of traditional approaches, most researchers have only addressed these decisions sequentially or independently. In this study, a hierarchical genetic algorithm is developed to simultaneously form manufacturing cells and determine the group layout of a CMS. The intrinsic features of our proposed algorithm include a hierarchical chromosome structure to encode two important cell design decisions, a new selection scheme to dynamically consider two correlated fitness functions, and a group mutation operator to increase the probability of mutation. From the computational analyses, these proposed structure and operators are found to be effective in improving solution quality as well as accelerating convergence.     

二阶算子矩阵代数中的全可导点Ⅱ

研究二阶算子矩阵代数中的全可导点.利用线性映射于算子矩阵代数运算,以及套代数理论的相关结果.给出并证明了E=[■](V是可逆算子)是二阶算子矩阵代数的关于强算子拓扑的全可导点,推广了相关文献的结果.     

Special operator equations

The study addresses the matrix operator equations of a special form which are used in the theory of Markov chains. Solving the operator equations with stochastic transition probability matrices of large finite or even countably infinite size reduces to the case of stochastic matrices of small size. In particular, the case of ternary chains is considered in detail. A Markov model for crack growth in a composite serves as an example of application.     

An elementary proof of the restricted invertibility theorem

We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.     

Mapped barycentric Chebyshev differentiation matrix method for the solution of regular Sturm-Liouville problems

In this paper, using spectral differentiation matrix and an elimination treatment of boundary conditions, Sturm-Liouville problems (SLPs) are discretized into standard matrix eigenvalue problems. The eigenvalues of the original Sturm-Liouville operator are approximated by the eigenvalues of the corresponding Chebyshev differentiation matrix (CDM). This greatly improves the efficiency of the classical Chebyshev collocation method for SLPs, where a determinant or a generalized matrix eigenvalue problem has to be computed. Furthermore, the state-of-the-art spectral method, which incorporates the barycentric rational interpolation with a conformal map, is used to solve regular SLPs. A much more accurate mapped barycentric Chebyshev differentiation matrix (MBCDM) is obtained to approximate the Sturm-Liouville operator. Compared with many other existing methods, the MBCDM method achieves higher accuracy and efficiency, i.e., it produces fewer outliers. When a large number of eigenvalues need to be computed, the MBCDM method is very competitive. Hundreds of eigenvalues up to more than ten digits accuracy can be computed in several seconds on a personal computer.