Search

A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries of modulus 1 on the diagonal. An important fact that has been largely overlooked by the previous research into Hungarian scaling of linear systems is that a given matrix typically has a range of possible Hungarian scalings, and direct or iterative solvers may behave quite differently under each of these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, it is natural to ask whether a superior performing scaling can be obtained by searching within the set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix. Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hungarian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial pivoting and the improved stability of LU factorizations without pivoting. We additionally find that applying the max-balancing scaling before computing incomplete LU preconditioners improves the convergence rate of certain iterative methods. Our numerical experiments also show that the Hungarian scaling returned by the HSL code MC64 has performance very close to that of the optimal max-balanced Hungarian scaling, which further supports the use of this code in practice. [ABSTRACT FROM AUTHOR]

The Bunch--Parlett algorithm, the Bunch-Kaufman algorithm, the bounded Bunch-- Kaufman algorithm, and Aasen's algorithm are four well-kno wn methods for solving symmetric indefinite linear systems, yet the last three methods are known to suffer from potential numerical instability. In this work, we develop a randomized complete pivoting (RCP) algorithm for solving symmetric indefinite linear systems of equations. RCP is comparable to the Bunch-Kaufman algorithm and Aasen's algorithm in computational efficiency, but still enjoys theoretical element growth and bounded entries in the factorization comparable to that of the Bunch-Parlett algorithm, up to a theoretical failure probability that exponentially decays with an oversampling parameter. In terms of the boundedness of entries in L, the Bunch-Parlett algorithm, the bounded Bunch-Kaufman algorithm, and Aasen's algorithm have maxi

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]

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]

Multivariate polynomials are usually discussed in the framework of algebraic geometry. Solving problems in algebraic geometry usually involves the use of a Gröbner basis. This article shows that linear algebra without any Gröbner basis computation suffices to solve basic problems from algebraic geometry by describing three operations: multiplication, division, and elimination. This linear algebra framework will also allow us to give a geometric interpretation. Multivariate division will involve oblique projections, and a link between elimination and principal angles between subspaces (CS decomposition) is revealed. The main computational tool in this approach is the QR decomposition. [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]

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]

Let R be an arbitrary Euclidean domain and A be an n×n matrix of determinant 1 whose entries are elements of R. Gaussian elimination process based on Euclidean division algorithm (on R) allows one to write A as a product of elementary matrices over R. Suslin's stability theorem states that any n×n multivariate polynomial matrix of determinant 1 with n 3 can be written as a product of elementary matrices. This result fails when n = 2, and a counter-example was constructed by P. M. Cohn [Inst. Hautes ´ Etudes Sci. Publ. Math. 30 (1996), pp. 365­413]. In this paper, an algorithm is developed that determines precisely when a given matrix in SL2(R[x1,...,xm]) allows a factorization into elementary matrices and, if it does, expresses it as a product of elementary matrices. This algorithm has potential applications to signal processing, in which case the coefficient ring R is usually taken as a field or a ring Z of integers. Extending the idea used in this algorithm, we disprove a conjecture of Tolhuizen­Hollmann­Kalker regarding the realizability of a certain FIR filter. [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]

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]