Noninvertible maps and their embedding into higher dimensional invertible maps

The first part is devoted to a presentation of specific features of noninvertible maps with respect to the invertible ones. When embedded into a three-dimensional invertible map, the specific dynamical features of a plane noninvertible map are the germ of the three-dimensional dynamics, at least for sufficiently small absolute values of the embedding parameter. The form of the paper, as well as its contents, is approached from a non abstract point of view, in an elementary form from a simple class of examples.     

Toward the Calculation of Higher-Dimensional Stable Manifolds and Stable Sets for Noninvertible and Piecewise-Smooth Maps

This paper presents a new numerical method for computing global stable manifolds and global stable sets of nonlinear discrete dynamical systems. For a given map f:ℝ ^d →ℝ ^d , the proposed method is capable of yielding large parts of stable manifolds and sets within a certain compact region M⊂ℝ ^d . The algorithm divides the region M in sets and uses an adaptive subdivision technique to approximate an outer covering of the manifolds. In contrast to similar approaches, the method requires neither the system’s inverse nor its Jacobian. Hence, it can also be applied to noninvertible and piecewise-smooth maps. The successful application of the method is illustrated by computation of one- and two-dimensional stable manifolds and global stable sets.     

Symmetric Permutations for I-Matrices to Avoid Small Pivots During Incomplete Factorization

Incomplete LU–factorizations have been very successful as preconditioners for solving sparse linear systems iteratively. However, for unsymmetric, indefinite systems small pivots (or even zero pivots) are often very detrimental to the quality of the preconditioner. A fairly recent strategy to deal with this problem has been to permute the rows of the matrix and to scale rows and columns to produce an I–matrix, a matrix having elements of modulus one on the diagonal and elements of at most modulus one elsewhere. These matrices are generally more suited for incomplete LU–factorization. I–matrices are preserved by symmetric permutation, i.e. by applying the same permutation to rows and columns of a matrix. We discuss different approaches for constructing such permutations which aim at improving the sparsity and diagonal dominance of an initial block. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Difference Fields with Quantifier Elimination

This paper proves that a difference field (E, ) admits quantifierelimination if and only if E is an algebraically closed field,and is an integer power of the Frobenius automorphism. 1991Mathematics Subject Classification 03C60, 12H10.     

消元法与带积分号的恒等式（英）

In this paper, our discussion is based on Zeilberg's basic idca[1] and use an elimination in the non-commutative Weyl algebra to get the differential operator. Thereby we can obtain the algorithm of proving identities of the form (∫∞-∞ )F(x, y)dy= a(x).     

Partial Elimination

The partial elimination method of Tuff & Jennings is consideredfor the solution of large sparse sets of simultaneous equationsin which the coefficient matrix is symmetric and positive definite.Proposals are made Jo modify the diagonal elements involvedin the elimination part of the algorithm to ensure stability.Also the iterative part of the algorithm is converted from anaccelerated stationary process to a conjugate gradient technique.Some numerical tests indicate that the method is more efficientthan the standard conjugate gradient method, although more storagespace is required for computer implementation.     

Some Features of Gaussian Elimination with Rook Pivoting

Rook pivoting is a relatively new pivoting strategy used in Gaussian elimination (GE). It can be as computationally cheap as partial pivoting and as stable as complete pivoting. This paper shows some new attractive features of rook pivoting. We first derive error bounds for the LU factors computed by GE and show rook pivoting usually gives a highly accurate U factor. Then we show accuracy of the computed solution of a linear system by rook pivoting is essentially independent of row scaling of the coefficient matrix. Thus if the matrix is ill-conditioned due to bad row scaling a highly accurate solution can usually be obtained. Finally for a typical inversion method involving the LU factorization we show rook pivoting usually makes both left and right residuals for the computed inverse of a matrix small.     

淘汰式变权TOPSIS法

传统的TOPSIS法不能直接用于常见的淘汰选优的实际决策.提出淘汰式变权TOPSIS法,通过逐步淘汰明显较劣方案,调整符合决策人偏好的权重,可以更好地反映实际决策行为.实例分析表明该法是简单实用的.     

On the Robustness of Gaussian Elimination with Partial Pivoting

It has been recently shown that large growth factors might occur in Gaussian Elimination with Partial Pivoting (GEPP) also when solving some plausibly natural systems. In this note we argue that this potential problem could be easily solved, with much smaller risk of failure, by very small (and low cost) modifications of the basic algorithm, thus confirming its inherent robustness. To this end, we first propose an informal model with the goal of providing further support to the comprehension of the stability properties of GEPP. We then report the results of numerical experiments that confirm the viewpoint embedded in the model. Basing on the previous observations, we finally propose a simple scheme that could be turned into (even more) accurate software for the solution of linear systems.     

Ein Problem der Elimination

Ohne Zusammenfassung     

Elimination techniques and interpolation

A general recurrence interpolation formula due to Gasca and López-Carmona (J. Approx. Th. 34 (1982)) is studied by means of elimination techniques in linear systems. The repeated application of this formula is investigated in order to show its equivalence with extrapolation methods.     

Bulk-Synchronous Parallel Gaussian Elimination

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of Gaussian elimination and related problems. First, we analyze the Gaussian elimination without pivoting, which can be applied to the LU decomposition of symmetric positive-definite or diagonally dominant real matrices. Then we analyze the Gaussian elimination with Schönhage's recursive local pivoting suitable for the LU decomposition of matrices over a finite field, and for the QR decomposition of real matrices by the Givens rotations. Both versions of Gaussian elimination can be performed with an optimal amount of local computation, but optimal communication and synchronization costs cannot be achieved simultaneously. The algorithms presented in the paper allow one to trade off communication and synchronization costs in a certain range, achieving optimal or near-optimal cost values at the extremes. Bibliography: 19 titles.     

Elimination theory and Newton polytopes

We study elimination theory in the context of Newton polytopes and develop its convex-geometry counterpart. Research of A. Esterov was supported in part by the grants RFBR-JSPS-06-01-91063, RFBR-07-01-00593, and INTAS-05-7805. Research of A. Khovanskii was supported in part by the grant OGP 0156833 (Canada).     

Elimination of quantifiers for modules

Every first-order formula in the language ofR-modules (R an associative ring) is equivalent relative to the theory ofR-modules to a boolean combination of positive primitive formulas and ∀∃-sentence. Supported by Schweizerischer Nationalfonds.     

关于高斯消去法的主元估计

本文证明了对任意一个给定的6阶实阵 A=(a_(ij)),若其中|a_(ij)|≤1,则有 P_6<6.7883.对于一般 n 阶矩阵,本文给出了估计 P_n 的一个改进方法.     

Overconvergent Real Closed Quantifier Elimination

Let K be the (real closed) field of Puiseux series in t overR endowed with the natural linear order. Then the elements ofthe formal power series rings [[₁,...,_n]] converge t-adicallyon [–t,t]ⁿ, and hence define functions [–t,t]ⁿ K. Let L be the language of ordered fields, enriched with symbolsfor these functions. By Corollary 3.15, K is o-minimal in L.This result is obtained from a quantifier elimination theorem.The proofs use methods from non-Archimedean analysis. 2000 MathematicsSubject Classification 03C64, 32P05, 32B05, 32B20, 03C10 (primary),03C98, 03C60, 14P15 (secondary).     

The Elimination of Integer Variables

It is pointed out that the projection of a Linear Programme (LP) into a lower dimension still results in an LP. For an Integer Programme (IP) this is not generally the case. Circumstances in which the projection (after eliminating integer variables) is still an IP are given.     

Perfect Elimination and Chordal Bipartite Graphs

We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal.