Some algorithms for inversion of linear dynamic systems

We study the problem of inversion of linear finite-dimensional dynamic systems in terms of the output. For different types of systems we propose several algorithms for inversion. We study the stability of the algorithms with respect to various perturbations. Translated fromAlgoritmy Upravleniya i Identifikatsii, pp. 156–167, 1997.     

Convergence of Non-stationary Parallel Multisplitting Methods for Hermitian Positive Definite Matrices

Non-stationary multisplitting algorithms for the solution of linear systems are studied. Convergence of these algorithms is analyzed when the coefficient matrix of the linear system is hermitian positive definite. Asynchronous versions of these algorithms are considered and their convergence investigated.

     

Shadow block iteration for solving linear systems obtained from wavelet transforms

Matrices resulting from wavelet transforms have a special “shadow” block structure, that is, their small upper left blocks contain their lower frequency information. Numerical solutions of linear systems with such matrices require special care. We propose shadow block iterative methods for solving linear systems of this type. Convergence analysis for these algorithms are presented. We apply the algorithms to three applications: linear systems arising in the classical regularization with a single parameter for the signal de-blurring problem, multilevel regularization with multiple parameters for the same problem and the Galerkin method of solving differential equations. We also demonstrate the efficiency of these algorithms by numerical examples in these applications.     

Convergence of the parallel chaotic waveform relaxation method for stiff systems

In this paper, we establish several algorithms for parallel chaotic waveform relaxation methods for solving linear ordinary differential systems based on some given models. Under some different assumptions on the coefficient matrix A and its multisplittings we obtain corresponding sufficient conditions of convergence of the algorithms. Also a discussion on convergence speed comparison of synchronous and asynchronous algorithms is given.     

The least-squares method for matrices dependent on parameters

Some algorithms are suggested for constructing pseudoinverse matrices and for solving systems with rectangular matrices whose entries depend on a parameter in polynomial and rational ways. The cases of one- and two-parameter matrices are considered. The construction of pseudoinverse matrices are realized on the basis of rank factorization algorithms. In the case of matrices with polynomial occurrence of parameters, these algorithms are the ΔW-1 and ΔW-2 algorithms for one- and two-parameter matrices, respectively. In the case of matrices with rational occurrence of parameters, these algorithms are the irreducible factorization algorithms. This paper is a continuation of the author's studies of the solution of systems with one-parameter matrices and an extension of the results to the case of two-parameter matrices with polynomial and rational entries. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 176–185. This work was supported by the Russian Foundation of Fundamental Research (grant 94-01-00919). Translated by V. N. Kublanovskaya.     

Techniques for bounding the convergence rate of genetic algorithms

The main purpose of the present paper is the study of computational aspects, and primarily the convergence rate, of genetic algorithms (GAs). Despite the fact that such algorithms are widely used in practice, little is known so far about their theoretical properties, and in particular about their long‐term behavior. This situation is perhaps not too surprising, given the inherent hardness of analyzing nonlinear dynamical systems, and the complexity of the problems to which GAs are usually applied. In the present paper we concentrate on a number of very simple and natural systems of this sort, and show that at least for these systems the analysis can be properly carried out. Various properties and tight quantitative bounds on the long‐term behavior of such systems are established. It is our hope that the techniques developed for analyzing these simple systems prove to be applicable to a wider range of genetic algorithms, and contribute to the development of the mathematical foundations of this promising optimization method. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 111–138, 1999     

Algorithms of filtration and extrapolation for discrete-time dynamical systems

The bases of theory and the recursive filtration algorithms ensuring the guaranteed precision of estimate for an extrapolated state of a dynamic system are described. A determined precision is ensured by corresponding choice of algorithm parameters.The different algorithms of filtration and extrapolation are investigated. These algorithms may be used in constructing tracking systems, organizing of corresponding measurements and estimation of parameters in information systems.     

Convergence of Metropolis-type algorithms for a large canonical ensemble

In this paper, we study the convergence of Metropolis-type algorithms used in modeling statistical systems with a fluctuating number of particles located in a finite volume. We justify the use of Metropolis algorithms for a particular class of such statistical systems. We prove a theorem on the geometric ergodicity of the Markov process modeling the behavior of an ensemble with a fluctuating number of particles in a finite volume whose interaction is described by a potential bounded below and decreasing according to the law r ^?3?α, α ≥ 0, as r → 0.     

Successive column correction algorithms for solving sparse nonlinear systems of equations

This paper presents two algorithms for solving sparse nonlinear systems of equations: the CM-successive column correction algorithm and a modified CM-successive column correction algorithm. Aq-superlinear convergence theorem and anr-convergence order estimate are given for both algorithms. Some numerical results and the detailed comparisons with some previously established algorithms show that the new algorithms have some promise of being very effective in practice.This research was partially supported by contracts and grants: DOE DE-AS05-82ER1-13016, AFOSR 85-0243 at Rice University, Houston, U.S.A. and Natural Sciences and Engineering Research Council of Canada grant A-8639.     

无穷迭代函数系统的遍历定理

度量空间的压缩映射的一个集合称为一个迭代函数系统．凝聚迭代函数系统可以被看成无穷迭代函数系统．研究了紧度量空间上的无穷迭代函数系统．利用Banach极限的特性和均匀压缩性,证明了紧度量空间上无穷迭代函数系统的随机迭代算法满足遍历性．于是,凝聚迭代函数系统的随机迭代算法也满足遍历性．     

Parallel algorithms for Gröbner-basis construction

The problem of the Gröbner-basis construction is important both from the theoretical and applied points of view. As examples of applications of Gröbner bases, one can mention the consistency problem for systems of nonlinear algebraic equations and the determination of the number of solutions to a system of nonlinear algebraic equations. The Gröbner bases are actively used in the constructive theory of polynomial ideals and at the preliminary stage of numerical solution of systems of nonlinear algebraic equations. Unfortunately, many real examples cannot be processed due to the high computational complexity of known algorithms for computing the Gröbner bases. However, the efficiency of the standard basis construction can be significantly increased in practice. In this paper, we analyze the known algorithms for constructing the standard bases and consider some methods for increasing their efficiency. We describe a technique for estimating the efficiency of paralleling the algorithms and present some estimates.     

Computational acceleration of projection algorithms for the linear best approximation problem

This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.     

Dynamic programming and Lagrange multipliers for active relaxation of resources in nonlinear non-equilibrium systems

In power production problems maximum power and minimum entropy production and inherently connected by the Gouy–Stodola law. In this paper various mathematical tools are applied in dynamic optimization of power-maximizing paths, with special attention paid to nonlinear systems. Maximum power and/or minimum entropy production are governed by Hamilton–Jacobi–Bellman (HJB) equations which describe the value function of the problem and associated controls. Yet, in many cases optimal relaxation curve is non-exponential, governing HJB equations do not admit classical solutions and one has to work with viscosity solutions. Systems with nonlinear kinetics (e.g. radiation engines) are particularly difficult, thus, discrete counterparts of continuous HJB equations and numerical approaches are recommended. Discrete algorithms of dynamic programming (DP), which lead to power limits and associated availabilities, are effective. We consider convergence of discrete algorithms to viscosity solutions of HJB equations, discrete approximations, and the role of Lagrange multiplier λ associated with the duration constraint. In analytical discrete schemes, the Legendre transformation is a significant tool leading to original work function. We also describe numerical algorithms of dynamic programming and consider dimensionality reduction in these algorithms. Indications showing the method potential for other systems, in particular chemical energy systems, are given.     

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.     

Integer extended ABS algorithms and possible control of intermediate results for linear Diophantine systems

We present a new class of integer extended ABS algorithms for solving linear Diophantine systems. The proposed class contains the integer ABS (the so-called EMAS and our proposed MEMAS) algorithms and the generalized Rosser’s algorithm as its members. After an application of each member of the class a particular solution of the system and an integer basis for the null space of the coefficient matrix are at hand. We show that effective algorithms exist within this class by appropriately setting the parameters of the members of the new class to control the growth of intermediate results. Finally, we propose two effective heuristic rules for selecting certain parameters in the new class of integer extended ABS algorithms.      

Multipreconditioning for nonsymmetric problems: The case of orthomin and biCG

Preconditioned Krylov subspace methods [7] are powerful tools for solving linear systems but sometimes they converge very slowly, and often after a long stagnation. A natural way to fix this is by enlarging the space in which the solution is computed at each iteration. Following this idea, we propose in this note two multipreconditioned algorithms: multipreconditioned orthomin and multipreconditioned biCG, which aim at solving general nonsingular linear systems in a small number of iterations. After describing the algorithms, we illustrate their behaviour on systems arising from the FETI domain decomposition method, where in order to enlarge the search space, each local component in the usual preconditioner is kept as a separate preconditioner.     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

Efficient spectral ultraspherical-Galerkin algorithms for the direct solution of 2nth-order linear differential equations

Some efficient and accurate algorithms based on the ultraspherical-Galerkin method are developed and implemented for solving 2nth-order linear differential equations in one variable subject to homogeneous and nonhomogeneous boundary conditions using a spectral discretization. We extend the proposed algorithms to solve the two-dimensional 2nth-order differential equations. The key to the efficiency of these algorithms is to construct appropriate base functions, which lead to linear systems with specially structured matrices that can be efficiently inverted, hence greatly reducing the cost and roundoff errors.     

Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation

We propose a family of retrospective optimization (RO) algorithms for optimizing stochastic systems with both integer and continuous decision variables. The algorithms are continuous search procedures embedded in a RO framework using dynamic simplex interpolation (RODSI). By decreasing dimensions (corresponding to the continuous variables) of simplex, the retrospective solutions become closer to an optimizer of the objective function. We present convergence results of RODSI algorithms for stochastic “convex” systems. Numerical results show that a simple implementation of RODSI algorithms significantly outperforms some random search algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).