Search

In 2007 Cortés and Peña introduced a pivoting strategy for the Neville elimination of nonsingular sign regular matrices and called it two-determinant pivoting. Neville elimination has been very useful for obtaining theoretical and practical properties for totally positive (negative) matrices and other related types of matrices. A real matrix is said to be almost strictly sign regular if all its nontrivial minors of the same order have the same strict sign. In this paper, some nice properties related with the application of Neville elimination with two-determinant pivoting strategy to almost strictly sign regular matrices are presented. [ABSTRACT FROM AUTHOR]

Abstract: Neville elimination is a direct method for the solution of linear systems of equations with advantages for some classes of matrices and in the context of pivoting strategies for parallel implementations. The growth factor is an indicator of the numerical stability of an algorithm. In the literature, bounds for the growth factor of Neville elimination with some pivoting strategies have appeared. In this work, we determine all the matrices such that the minimal upper bound of the growth factor of Neville elimination with those pivoting strategies is reached. [Copyright &y& Elsevier]

The minimum edge count (MEC) and optimal Jacobian accumulation problems in linearized directed acyclic graphs (DAGs) result from the combinatorics induced by the associativity of the chain rule of differential calculus. This paper discusses a suitable graph formalism followed by proving a number of results that yield a considerable search space reduction for both problems. An algorithmic link between numerical analysis and theoretical computer science is established. Although both problems are believed to be NP-hard in general, a linear-time algorithm is presented solving the MEC problem for a specified subclass of l-DAGs. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we present two new algorithmic variants to compute the Neville elimination, with and without pivoting, which improve data locality and cast most of the computations in terms of high-performance Level 3 BLAS. The experimental evaluation on a state-of-the-art multi-core processor demonstrates that the new blocked algorithms exhibit a much higher degree of concurrency and better cache usage, yielding higher performance while offering numerical accuracy akin to that of the traditional columnwise variant in most cases. [Copyright &y& Elsevier]

Abstract: We propose an elimination mechanism in the study of the evolutionary prisoner’s dilemma games on evolving networks. It assumes that after each round of playing, players whose payoffs are below a certain threshold will be eliminated from the game and the same number of new nodes will be added to the network to maintain the size of the network constant. Numerical results show that moderate values of elimination threshold can result in a maximum cooperation level in the evolutionary prisoner’s dilemma game. Moreover, the elimination mechanism can make the network structure evolve into a high heterogeneity in degree distribution, which is considered to be helpful in promoting cooperation in evolutionary games. The present study may provide new insight for understanding the evolution of cooperation in light of the law ‘survival of the fittest’ in nature. [Copyright &y& Elsevier]

Based on the mechanized mathematics and WU Wen-tsun elimination method, using oil film forces of short-bearing model and Muszynska’s dynamic model, the dynamical behavior of rotor-bearing system and its stability of motion are investigated. As example, the concept of Wu characteristic set and Maple software, whirl parameters of short-bearing model, which is usually solved by the numerical method, are analyzed. At the same time, stability of zero solution of Jeffcott rotor whirl equation and stability of self-excited vibration are studied. The conditions of stable motion are obtained by using theory of nonlinear vibration. [ABSTRACT FROM AUTHOR]

Copyright of Archive of Mechanical Engineering is the property of Polish Academy of Sciences and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Recently, Liu and Wang [Q. Liu and M. Wang, Algebraic properties and perturbation results for the indefinite least squares problem with equality constraints, Int. J. Comp. Math. 87(2) (2010), pp. 425-434.] proved that the solution of the equality constrained indefinite least squares (ILSE) problem min Bx=d(b-Ax)TJ(b-Ax), J=diag(-Iq, Ip) is the limit of the solution of the unconstrained weighted indefinite least squares (WILS) problem [image omitted] and J˜=diag(Is, J) as the weight μ tends to infinity, assuming that B has full row rank and xTATJAx>0 for all nonzero x∈null (B). Based on this observation, we derive a type of elimination method by applying the hyperbolic QR factorization method to above WILS problem and taking the limit analytically. Theoretical analysis shows that the method obtained is forward stable under a reasonable assumption. We illustrate our results with numerical tests. [ABSTRACT FROM AUTHOR]

The article provides a stable test to check the matrix's strictly sign regularity (SSR). It says that Neville elimination with two-determinant pivoting strategy and MATLAB with floating point arithmetic of finite precision for numerical experiments have been used to assess the SSR matrix. It mentions that the growth factor of Neville elimination with pivoting strategy has shown better behavior while Neville elimination without permutations needs 11 digits to obtain SSR matrix.

It is well known that the solution of the equality constrained least squares (LSE) problem minBx =d b - Ax 2 is the limit of the solution of the unconstrained weighted least squares problem min x µd b - µB A x 2 as the weight µ tends to infinity, assuming that [ BT AT ]T has full rank. We derive a method for the LSE problem by applying Householder QR factorization with column pivoting to this weighted problem and taking the limit analytically, with an appropriate rescaling of rows. The method ob- tained is a type of direct elimination method. We adapt existing error analysis for the unconstrained problem to obtain a row-wise backward error bound for the method. The bound shows that, provided row pivoting or row sorting is used, the method is well-suited to problems in which the rows of A and B vary widely in norm. As a by-product of our analysis, we derive a row-wise backward error bound of precisely the same form for the standard elimination method for solving the LSE problem. We illustrate our results with numerical tests. [ABSTRACT FROM AUTHOR]

In this paper we introduce and analyse a new Schur complement approximation based on incomplete Gaussian elimination. The approximate Schur complement is used to develop a multigrid method. ibis multigrid method has an algorithmic structure that is very similar to the algorithmic structure of classical multigrid methods. The resulting method is almost purely algebraic and has increasing robustness properties with respect to variation in problem parameters. [ABSTRACT FROM AUTHOR]

We report on our on-going efforts to apply real quantifier elimination to the synthesis of optimal numerical algorithms. In particular, we describe a case study on the square root problem: given a real number x and an error bound ε , find a real interval such that it contains x and its width is less than or equal to ε . A typical numerical algorithm starts with an initial interval and repeatedly updates it by applying a “refinement map” on it until it becomes narrow enough. Thus the synthesis amounts to finding a refinement map that ensures the correctness and optimality of the resulting algorithm. This problem can be formulated as a real quantifier elimination. Hence, in principle, the synthesis can be carried out automatically. However, the computational requirement is huge, making the automatic synthesis practically impossible with the current general real quantifier elimination software. We overcame the difficulty by (1) carefully reducing a complicated quantified formula into several simpler ones and (2) automatically eliminating the quantifiers from the resulting ones using the state-of-the-art quantifier elimination software. As the result, we were able to synthesize semi-automatically an optimal quadratically 1 convergent map, which is better than the well known hand-crafted Secant-Newton map. Interestingly, the optimal synthesized map is not contracting as one would naturally expect. [ABSTRACT FROM AUTHOR]

In a rotating spherical shell, an inviscid inertia-free flow driven by an arbitrary body force will have cylindrical components that are either discontinuous across, or singular on, the tangent cylinder, the cylinder tangent to the inner core and parallel to the rotation axis. We investigate this problem analytically, and show that there is an infinite hierarchy of constraints on this body force which, if satisfied, sequentially remove discontinuities or singularities in flow derivatives of progressively higher order. By splitting the solution into its equatorial symmetry classes, we are able to provide analytic expressions for the constraints and demonstrate certain inter-relations between them. We show numerically that viscosity smoothes any singularity in the azimuthal flow component into a shear layer, comprising inner and outer layers, either side of the tangent cylinder, of width O(E2/7) and O(E1/4), respectively, where E is the Ekman number. The shear appears to scale as O(E-1/3) in the equatorially symmetric case, although in a more complex fashion when considering equatorial antisymmetry, and attains a maximum value in either the inner or outer sublayers depending on equatorial symmetry. In the low-viscosity magnetohydrodynamic system of the Earth's core, magnetic tension within the fluid resists discontinuities in the flow and may dynamically adjust the body force in order that a moderate number of the constraints are satisfied. We speculate that it is violations of these constraints that excites torsional oscillations, magnetohydrodynamic waves that are observed to emanate from the tangent cylinder. [ABSTRACT FROM AUTHOR]

Abstract: Elimination is a basic algebraic operation which geometrically corresponds to projections. This article describes using the numerical algebraic geometric concept of witness sets to compute the projection of an algebraic set. The ideas described in this article apply to computing the image of an algebraic set under any linear map. [Copyright &y& Elsevier]

Abstract: A numerical elimination method is presented in this paper for floating-point computation in polynomial algebra. The method is designed to calculate one or more polynomials in an elimination ideal by a sequence of matrix rank/kernel computation. The method is reliable in numerical computation with verifiable stability and a sensitivity measurement. Computational experiment shows that the method possesses significant advantages over classical resultant computation in numerical stability and in producing eliminant polynomials with lower degrees and fewer extraneous factors. The elimination algorithm combined with an approximate GCD finder appears to be effective in solving polynomial systems for positive dimensional solutions. [Copyright &y& Elsevier]

We derive a unified representation for all types of generalized inverses related to the {1}-inverse. Based on this representation, we propose a unified Gauss–Jordan elimination procedure for the computation of all types of generalized inverses related to the {1}-inverse. Complexity analysis indicates that when applied to compute the Moore–Penrose inverse, our method is more efficient than the existing Gauss–Jordan elimination methods in the literature for a large class of problems. Finally, numerical experiments show our method for Moore–Penrose inverse has good efficiency and accuracy, and especially for computing the Moore–Penrose inverse of m × n matrices with m < n our method gives the best performance in practice. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we have used a complete pivoting strategy to compute the left-looking version of preconditioner. This pivoting is based on the complete pivoting strategy of the version of Gaussian Elimination process. There is a parameter to control the pivoting process. To study the effect of on the quality of the left-looking version of preconditioner with complete pivoting strategy, we have used ten different values of this parameter. In the numerical experiments section, the quality of the left-looking version of preconditioner with complete pivoting strategy has been compared to the quality of the right-looking version of this preconditioner. [Copyright &y& Elsevier]

Abstract: In this paper we consider diagonally dominant tridiagonal matrices whose diagonals come from smooth functions. It is shown that the Schur complements or pivots that arise from Gaussian elimination of these matrices can be given point-wise limits on a grid as the matrices grow in size to infinity. Numerical results are presented to verify the theory. [Copyright &y& Elsevier]

Abstract: In this work, a method for solving inhomogeneous nonlocal fractional heat equations is proposed. The method is based on the modified Gauss elimination method. It is proved by using matrix stability approach that the method is unconditionally stable. Numerical results are provided to illustrate the accuracy and efficiency of the proposed method. [Copyright &y& Elsevier]

Abstract: In the proof-theoretic study of logic, the notion of normal proof has been understood and investigated as a metalogical property. Usually we formulate a system of logic, identify a class of proofs as normal proofs, and show that every proof in the system reduces to a corresponding normal proof. This paper develops a system of modal logic that is capable of expressing the notion of normal proof within the system itself, thereby making normal proofs an inherent property of the logic. Using a modality △ to express the existence of a normal proof, the system provides a means for both recognizing and manipulating its own normal proofs. We develop the system as a sequent calculus with the implication connective ⊃ and the modality △, and prove the cut elimination theorem. From the sequent calculus, we derive two equivalent natural deduction systems. [Copyright &y& Elsevier]

Abstract: This paper presents an efficient numerical method for observability analysis of systems including both conventional (SCADA) measurements and synchronized phasor (PMU) measurements, using integer preserving Gaussian elimination of integer coefficient matrices. The observable islands are identified in a noniterative manner, by performing backward substitutions on the integer triangular factors of the integer gain matrix. Multiple placement of conventional and phasor measurements for a system that is found to be unobservable is done by a direct method, using the integer triangular factors of a Gram matrix associated with a reduced size Jacobian matrix. Since all computations performed are exact, no round-off error, numerical instability, or zero identification problems occur. The IEEE 14-bus system is used to illustrate the steps of the proposed method. Test results for the IEEE 300-bus and the FRCC 3949-bus systems are provided to demonstrate the features of the proposed algorithms. [Copyright &y& Elsevier]

In this paper we present a novel improvement of Wilkinson's iterative refinement for the solution of linear system by using stability results of numerical solution for a dynamic system associated with the linear system. The convergence analysis is shown and roundoff error analysis is considered for this new refinement. Numerical experiments are accompanied to support our analysis. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm. [Copyright &y& Elsevier]