Search

Lagrange–Vandermonde matrices are the collocation matrices corresponding to Lagrange‐type bases, obtained by removing the denominators from each element of a Lagrange basis. It is proved that, provided the nodes required to create the Lagrange‐type basis and the corresponding collocation matrix are properly ordered, such matrices are strictly totally positive. A fast algorithm to compute the bidiagonal decomposition of these matrices to high relative accuracy is presented. As an application, the problems of eigenvalue computation, linear system solving and inverse computation are solved in an efficient and accurate way for this type of matrices. Moreover, the proposed algorithms allow to solve fastly and to high relative accuracy some of the cited problems when the involved matrices are collocation matrices corresponding to the standard Lagrange basis, although such collocation matrices are not totally positive. Numerical experiments illustrating the good performance of our approach are also included. [ABSTRACT FROM AUTHOR]

The concept of depth of an almost strictly sign regular matrix is introduced and used to simplify some algorithmic characterizations of these matrices. [ABSTRACT FROM AUTHOR]

A fast and accurate algorithm to compute the bidiagonal decomposition of collocation matrices of the Lupaş-type (p,q)-analogue of the Bernstein basis is presented. The error analysis of the algorithm and the perturbation theory for the bidiagonal decomposition are also included. Starting from this bidiagonal decomposition, the accurate and efficient solution of several linear algebra problems involving these matrices is addressed: linear system solving, eigenvalue and singular value computation, and computation of the inverse and the Moore-Penrose inverse. The numerical experiments carried out show the good behaviour of the algorithm. [ABSTRACT FROM AUTHOR]

An inverse central ordering of the nodes is proposed for the Newton interpolation formula. This ordering may improve the stability for certain distributions of nodes. For equidistant nodes, an upper bound of the conditioning is provided. This bound is close to the bound of the conditioning in the Lagrange interpolation formula, whose conditioning is the lowest. This ordering is related to a pivoting strategy of a matrix elimination procedure called Neville elimination. The results are illustrated with examples. [ABSTRACT FROM AUTHOR]

In this work, several algorithms have been implemented with Matlab to obtain an algorithmic characterizations of almost strictly sign regular matrices using Neville elimination. [ABSTRACT FROM AUTHOR]

A fast and accurate algorithm to compute the bidiagonal decomposition of rectangular totally positive h-Bernstein-Vandermonde matrices is presented. The error analysis of the algorithm and the perturbation theory for the bidiagonal decomposition of totally positive h-Bernstein-Vandermonde matrices are addressed. The computation of this bidiagonal decomposition is used as the first step for the accurate and efficient computation of the singular values of rectangular totally positive h-Bernstein-Vandermonde matrices and for solving least squares problems whose coefficient matrices are such matrices. [ABSTRACT FROM AUTHOR]

An algorithm for the computation of the bidiagonal decomposition of strictly totally positive h-Bernstein-Vandermonde matrices is presented. These matrices are collocation matrices of h-Bernstein bases (a generalization of the Bernstein basis) of the space of polynomials of degree less than or equal to n. The algorithm is fast (its computational complexity is O (n 2)) and has high relative accuracy. The computation of this bidiagonal decomposition is used as the initial stage for the accurate and efficient solution of several linear algebra problems with these matrices: linear system solving, eigenvalue computation and inverse computation. Numerical experiments are also included. [ABSTRACT FROM AUTHOR]

Abstract In this paper some properties of two-determinant pivoting for Neville elimination are presented. In particular, we consider a zero-increasing property and we show an optimal normwise growth factor. Comparisons with other pivoting strategies for Neville elimination and with Gaussian elimination with partial pivoting of almost strictly sign regular matrices are performed. Numerical examples are included. [ABSTRACT FROM AUTHOR]

Abstract The computation of the Moore–Penrose inverse of structured strictly totally positive matrices is addressed. Since these matrices are usually very ill-conditioned, standard algorithms fail to provide accurate results. An algorithm based on the Q R factorization and which takes advantage of the special structure and the totally positive character of these matrices is presented. The first stage of the algorithm consists of the accurate computation of the bidiagonal decomposition of the matrix. Numerical experiments illustrating the good behavior of our approach are included. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we provide algorithms for computing the bidiagonal decomposition of the collocation matrices of a very general class of bases of interest in computer‐aided geometric design and approximation theory. It is also shown that these algorithms can be used to perform accurately some algebraic computations with these matrices, such as the calculation of their inverses, their eigenvalues, or their singular values. Numerical experiments illustrate the results. [ABSTRACT FROM AUTHOR]

Cauchy–Vandermonde matrices play a fundamental role in rational interpolation theory and in other fields. When all their corresponding nodes are different and positive and all poles are different and negative and follow adequate orderings, these matrices are totally positive. In this paper we provide fast algorithms for computing bidiagonal factorizations of these matrices and their inverses with high relative accuracy. These algorithms can be used to solve with high relative accuracy other algebraic problems, such as the computation of all singular values, all eigenvalues or the solution of certain linear systems. The error analysis of the algorithm for computing the bidiagonal factorization and the corresponding perturbation theory are also performed. [ABSTRACT FROM AUTHOR]

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]

An algorithm for computing the bidiagonal decomposition of Said–Ball–Vandermonde matrices in the rectangular case is presented, which allows one to use known algorithms for totally positive matrices represented by their bidiagonal decomposition. The algorithm is fast and possesses high relative accuracy. The error analysis of the algorithm is also addressed, along with the perturbation theory for the bidiagonal factorization of totally positive Said–Ball–Vandermonde matrices. Some numerical experiments showing the good behavior of the algorithm are included. [ABSTRACT FROM AUTHOR]

A real matrix A = ( a i j ) 1 ≤ i , j , ≤ n is said to be almost strictly totally negative if it is almost strictly sign regular with signature ε = ( − 1 , − 1 , … , − 1 ) , which is equivalent to the property that all its nontrivial minors are negative. In this paper an algorithmic characterization of nonsingular almost strictly totally negative matrices is presented. [ABSTRACT FROM AUTHOR]

An algorithmic characterization of the nonsingular almost strictly sign regular matrices by Neville elimination is presented. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the class of rectangular matrices that admit bidiagonal-type factorizations by Neville elimination without exchanges. We provide a complete characterization for a rectangular matrix to be factored as a product of bidiagonal factors and a banded factor in terms of rank structure properties. Consequently, we give a complete characterization of the class of rectangular matrices that have Neville factorizations. [ABSTRACT FROM AUTHOR]

Neville elimination is an elimination procedure alternative to Gaussian elimination and very adequate when dealing with some special classes of matrices. In this paper, we present pivoting strategies such that the radii of the Geršgorin circles of the Schur complements through Neville elimination with these pivoting strategies reduce their length and we consider classes of matrices important in many applications. We include illustrative examples comparing the results with those obtained with Gaussian elimination and showing that our hypotheses are necessary. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we perform a backward error analysis of Neville elimination whenever there need row exchanges. Componentwise backward error bounds are presented for this elimination procedure applied to any nonsingular matrices. Consequently, it is shown that Neville elimination with two-determinant pivoting proposed by Cortes and Peña (2007) [5] is an excellent method for the triangularization of nonsingular sign regular matrices including totally nonnegative and totally nonpositive matrices, which has a pleasantly small componentwise relative backward error. In particular, a small componentwise relative error bound is also provided for the bidiagonal factorization of totally nonnegative matrices. [Copyright &y& Elsevier]

Abstract: It is well known that a totally nonnegative matrix can be characterized in terms of its bidiagonal factorization, which is critical to perform accurate computations. However, there is no known such factorization of other sign regular matrices. In this paper, we provide a characterization and test for certain sign regular matrices with the same signature sequence as that of nonsingular Jacobi sign regular matrices. Consequently, a bidiagonal factorization is derived for such sign regular matrix, which, in turn, provides an effective way to generate these sign regular matrices. [Copyright &y& Elsevier]

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]

This paper analyses the performance of several versions of a block parallel algorithm in order to apply Neville elimination in a distributed memory parallel computer. Neville elimination is a procedure to transform a square matrix A into an upper triangular one. This analysis must take into account the algorithm behaviour as far as execution time, efficiency and scalability are concerned. Special attention has been paid to the study of the scalability of the algorithms trying to establish the relationship existing between the size of the block and the performance obtained in this metric. It is important to emphasize the high efficiency achieved in the studied cases and that the experimental results confirm the theoretical approximation. Therefore, we have obtained a high predicting ability tool of analysis. Finally, we will present the elimination of Neville as an efficient tool in detecting point sources in cosmic microwave background maps. [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: Neville elimination is a direct method for solving linear systems. Several pivoting strategies for Neville elimination, including pairwise pivoting, are analyzed. Bounds for two different kinds of growth factors are provided. Finally, an approximation of the average normalized growth factor associated with several pivoting strategies is computed and analyzed using random matrices. [ABSTRACT FROM AUTHOR]

Abstract: Neville elimination is an elimination procedure alternative to Gaussian elimination. It is very useful when dealing with totally positive matrices, for which nice stability results are known. Here we include examples, most of them test matrices used in MATLAB which are not totally positive matrices, where Neville elimination outperforms Gaussian elimination. [Copyright &y& Elsevier]

Solving linear systems is often required in chemical problems. Besides, birth and death processes occur in many chemical phenomena and the matrices associated to these processes are totally positive, that is, all their minors are nonnegative. Neville elimination is an elimination procedure very useful when dealing with these matrices. Convergence and stability of iterative refinement using Neville elimination are analyzed, in particular when the coefficient matrix is totally positive. Other applications to chemistry are commented and numerical experiments are shown. [ABSTRACT FROM AUTHOR]

Neville elimination is an elimination procedure that is very useful when dealing with totally positive matrices. We provide a sufficient condition for the convergence of the iterative refinement using Neville elimination. [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]

The scalability of a parallel system is a measure of its capacity to effectively use an increasing number of processors. Both the isoefficiency function and the scaled efficiency are metrics used to analyse the scalability of parallel algorithms and architectures. The first function relates the size of the problem being solved to the number of processors required to maintain efficiency at a fixed value, while the second function shows how an algorithm scales when both the size of the problem and the number of processors are increased. This paper models and measures the parallel scalability of the Neville method when a checkerboard partitioning is performed. Neville elimination is a method for solving a system of linear equations. This process appears naturally when the Neville strategy of interpolation is used to solve linear systems. The scaled efficiency of some algorithms of this method is studied on an IBM SP2 and also over an HP cluster. [ABSTRACT FROM AUTHOR]

Abstract: In this paper it is shown that Neville elimination is suited to exploit the rank structure of an order-r quasiseparable matrix by providing a condensed decomposition of A as product of unit bidiagonal matrices, all together specified by parameters, at the cost of flops. An application of this result for eigenvalue computation of totally positive rank-structured matrices is also presented. [Copyright &y& Elsevier]

Abstract: A pivoting strategy of operations for the Neville elimination of n × n nonsingular sign regular matrices is introduced. Among other nice properties, it is proved that it preserves sign regularity. It is also shown its relationship with scaled partial pivoting strategies for Neville elimination. [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]

It is well known that checkerboard partitioning can exploit more concurrency than striped partitioning because the matrix computation can be divided among more processors than in the case of striping. In this work we analyze the performance of Neville method when a checkerboard partitioning is used, focusing on the special case of block–cyclic-checkerboard partitioning. This method is an alternative to Gaussian elimination and it has been proved to be very useful for some classes of matrices, such as totally positive matrices. The performance of this parallel system is measured in terms of the efficiency (the fraction of time for which a processor is usefully employed) which in our model is close to one, when the optimum block size is used. Also, we have executed our algorithms on a Parallel PC cluster, observing that both efficiencies (theoretical and empirical) are quite similar. [Copyright &y& Elsevier]

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]

An m×n matrix A is sign regular if, for each k (1⩽k⩽min{m,n}), all k×k submatrices of A have determinant with the same nonstrict sign. The zero pattern of nonsingular sign regular matrices is analyzed. It is proved that the number of zero entries which can appear in a nonsingular sign regular matrix depends on its signature. A matrix is totally nonpositive if all its minors are nonpositive. A test for recognizing nonsingular totally nonpositive matrices is also provided. [Copyright &y& Elsevier]

In this paper we prove that Neville elimination can be matricially described by elementary matrices. A PLU-factorization is obtained for any n×m matrix, where P is a permutation matrix, L is a lower triangular matrix (product of bidiagonal factors) and U is an upper triangular matrix.This result generalizes the Neville factorization usually applied to characterize the totally positive matrices. We prove that this elimination procedure is an alternative to Gaussian elimination and sometimes provides a lower computational cost. [Copyright &y& Elsevier]