Search

The elimination tree model for sparse unsymmetric matrices and an algorithm for constructing it have been recently proposed by Eisenstat and Liu [SIAM J. Matrix Anal. Appl., 26 (2005), pp. 686-705] and [SIAM J. Matrix Anal. Appl., 29 (2008), pp. 1363-1381]. The construction algorithm has a worst-case time complexity of Θ(mn) for an n X n unsymmetric matrix having m off-diagonal nonzeros. We propose another algorithm that has a worst-case time complexity of ...(mlogn). We compare the two algorithms experimentally and show that both algorithms are efficient in general. The algorithm of Eisenstat and Liu is faster in many practical cases, yet there are instances in which there is a significant difference between the running time of the two algorithms in favor of the one proposed here. [ABSTRACT FROM AUTHOR]

We prove that the codes issued from the elimination of any sub-alphabet in a trace monoid are finite-state recognizable. This implies in particular that the transitive factorizations of the trace monoids are recognizable by (boolean) finite-state automata. [ABSTRACT FROM AUTHOR]

The height of the elimination tree has long acted as the only criterion for deriving a suitable fill-preserving sparse matrix ordering for parallel factorization. Although the deficiency in adopting height as the criterion for all circumstances was well recognized, no research has succeeded in alleviating this constraint. In this paper, we extend the unit-cost fill-preserving ordering into a generalized class that can adopt various aspects in parallel factorization, such as computation, communication, and algorithmic diversity. We recognize and show that if any cost function satisfies two mandatory properties, called the independence and conservation properties, a greedy ordering scheme then generates an optimal ordering with minimum completion cost. We also present an efficient implementation of the proposed ordering algorithm. Incorporating various techniques, the complexity can be improved from O (n log n+e) to O (q log q+$\kappa$), where n denotes the number of nodes, e the number of edges, q the number of maximal cliques, and $\kappa$ the sum of all maximal clique sizes in the filled graph. Empirical results show that the proposed algorithm can significantly reduce the parallel factorization cost without sacrificing much in terms of time efficiency. [ABSTRACT FROM AUTHOR]

An n × m real matrix A is a totally positive matrix if all its minors are nonnegative. The Neville elimination process is studied in relation to the existence of a totally positive factorization LS of a rectangular matrix. An LS factorization is obtained for a totally positive matrix, where L is a lower echelon form matrix, of size n × k, and S is an upper echelon form matrix, of size k × m, and both L and S are totally positive matrices. [ABSTRACT FROM AUTHOR]

Nonnegative tensor factorization has applications in statistics, computer vision, exploratory multiway data analysis, and blind source separation. A symmetric nonnegative tensor, which has an exact symmetric nonnegative factorization, is called a completely positive tensor. This concept extends the concept of completely positive matrices. A classical result in the theory of completely positive matrices is that a symmetric, diagonally dominated nonnegative matrix is a completely positive matrix. In this paper, we introduce strongly symmetric tensors and show that a symmetric tensor has a symmetric binary decomposition if and only if it is strongly symmetric. Then we show that a strongly symmetric, hierarchically dominated nonnegative tensor is a completely positive tensor, and present a hierarchical elimination algorithm for checking this. Numerical examples are given to illustrate this. Some other properties of completely positive tensors are discussed. In particular, we show that the completely positive tensor cone and the co-positive tensor cone of the same order are dual to each other. [ABSTRACT FROM AUTHOR]

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]

Recently, Evans [1] has given a variant of the classical Choleski factorization, called Choleski Q.I.F., for the solution of symmetric linear systems. In the present paper we address the questions of existence and stability of the factorization. We show that Evans' Choleski Q.I.F. exists if the coefficient matrix is symmetric positive definite. Our proof of existence of the factorization is via obtaining the diagonal elements of the factor matrices in a closed-form in terms of certain principal minors of the coefficient matrix. By interpreting the Choleski Q.I.F. as an elimination procedure in which eliminations are carried out, alternately, in columns from the left and the right, we show that the Choleski Q.I.F. is also (numerically) strongly stable if the coefficient matrix is symmetric positive definite. We include arithmetical operations counts for the Choleski Q.I.F.; these agree with the counts for the classical Choleski factorization. [ABSTRACT FROM AUTHOR]

In this paper, the well known singular value decomposition (SDV) method is extended to explicit (2 × 2) block form, by using the Quadrant Interlocking Factorisation (QIF) method. Numerical results are presented to portray the validity of the proposed method. [ABSTRACT FROM AUTHOR]

Let D be a diagonal matrix and Eij denote the n-by-n matrix with a 1 in entry (i,j) and 0 in every other entry. An n-by-n matrix A has a successively ordered elementary bidiagonal (SEB) factorization if it can be factored as [This symbol cannot be presented in ASCII format] in which Lj(sjk) = I + sjkEj,j -1 and Uj(tkj) = I + tkjEj -1,j for some scalars sjk,tkj. Note that some of the parameters sjk,tkj may be zero, and the order of the bidiagonal factors is fixed. If this factorization corresponds to reduction of A to D via successive row/column operations in the specified order, it is called an elimination SEB factorization. New rank conditions are formulated that are proved to be necessary and sufficient for matrix A to have such a factorization. These conditions are related to known but more restrictive properties that ensure a bidiagonal factorization as above, but with all parameters sjk,tkj nonzero. [ABSTRACT FROM AUTHOR]

This paper describes a domain-based multilevel block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU factorization with an algebraic multilevel recursive reduction. Thus, in the first level the matrix is permuted into a block form using (block) independent set ordering and an ILUT factorization for the reordered matrix is performed. The reduced system is the approximate Schur complement associated with the partitioning, and it is obtained implicitly as a by-product of the partial ILUT factorization with respect to the complement of the independent set. The incomplete factorization process is repeated with the reduced systems recursively. The last reduced system is factored approximately using ILUT again. The successive reduced systems are not stored. This implementation is efficient in controlling the fill-in elements during the multilevel block ILU factorization, especially when large size blocks are used in domain decomposition-type implementations. Numerical experiments are used to show the robustness and efficiency of the proposed technique for solving some difficult problems. [ABSTRACT FROM AUTHOR]

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]

The received wave held including primaries and all of the multiples can be associated with the reflection coefficients which are only primaries by a prediction operator and two equations: the energy flux conservation equation and the prediction operator equation that is developed from the Levinson recursion and can be easily solved by Li group method under a two-dimensional condition. Given reflection coefficients, the prediction operator can be obtained by solving the prediction operator equation. By the energy flux conservation equation, the reciprocal of the prediction operator times the conjugate of it, the wave held can be predicted, in which both of the surface multiples and the internal multiples are involved. On the other hand, if the wave held is given, based on the energy flux conservation equation solved by the 2D spectral factorization, a fully automated data-driven algorithm is developed to remove the surface multiples as well as the internal multiples. [ABSTRACT FROM AUTHOR]

Abstract: A real matrix A, of size , is called totally nonnegative (totally positive) if all its minors are nonnegative (positive). A variant of the Neville elimination process is studied in relation to the existence of a totally nonnegative elementary bidiagonal factorization of A. The class of quasi- oscillatory rectangular matrices, which in the square case contains the oscillatory matrices, is introduced and a characterization of this class of matrices, by incorporating bidiagonal factorization, is showed. [Copyright &y& Elsevier]

Abstract: The confluent Cauchy–Vandermonde matrices are considered, which were studied earlier by various authors in different way. In this paper, we analyze the factorization of the inverse of a special type of confluent Cauchy–Vandermonde matrix as a product of block bidiagonal matrices by using block Neville elimination. Factorizations of confluent Cauchy–Vandermonde matrices are also considered, which generalize the results of [J.J. Martinez, J.M. Pena, Factorizations of Cauchy–Vandermonde matrices, Linear Algebra Appl. 284 (1998) 229–237]. [Copyright &y& Elsevier]

Every real m × n matrix A can be factored in three ways that arise from the steps of elimination: a lower triangular/upper triangular factorization P A = L U , a column-row factorization A = C R , and a triple factorization A = C W − 1 B. The column-row factorization provides both a constructive proof that the row rank r of A equals the column rank, and a formula for the pseudoinverse A + not based on the singular value decomposition. In the triple factorization, C and B contain the first r independent columns of A and the first r independent rows of A ; W is the invertible submatrix of A where B meets C. An alternative to the traditional elimination method, using slide steps in place of the usual swap steps, identifies the first r independent rows of A. [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: Linear systems are usually solved with Gaussian elimination. Especially when multiple right hand sides are involved, an efficient procedure is to provide a factorization of the left hand side. When exact computations are required in an integral domain, complete fraction-free factorization and forward–backward substitutions are useful. This article deals with the case where the left hand side may be singular. In such a case, kernels are required to test a solvability condition and to derive the general form of the solutions. The complete fraction-free algorithms are therefore extended to deal with singular systems and to provide the kernels with exact computations on the same integral domain where the initial data take their entries. [Copyright &y& Elsevier]