na31 swMATH ID: 11500 Software Authors: Aricò, Antonio; Rodriguez, Giuseppe Description: A fast solver for linear systems with displacement structure. We describe a fast solver for linear systems with reconstructible Cauchy-like structure, which requires O(rn 2 ) floating point operations and O(rn) memory locations, where n is the size of the matrix and r its displacement rank. The solver is based on the application of the generalized Schur algorithm to a suitable augmented matrix, under some assumptions on the knots of the Cauchy-like matrix. It includes various pivoting strategies, already discussed in the literature, and a new algorithm, which only requires reconstructibility. We have developed a software package, written in Matlab and C-MEX, which provides a robust implementation of the above method. Our package also includes solvers for Toeplitz(+Hankel)-like and Vandermonde-like linear systems, as these structures can be reduced to Cauchy-like by fast and stable transforms. Numerical experiments demonstrate the effectiveness of the software. (netlib numeralgo na31) Homepage: http://www.netlib.org/numeralgo/index.html Dependencies: Matlab Keywords: displacement structure; Toeplitz(+Hankel)-like matrix; generalized Schur algorithm; augmented matrix; matlab toolbox; Cauchy-like matrix; Vandermonde-like linear systems; numerical experiments Related Software: drsolve; tpls; mctoolbox; toms729gw; smt; TOEPLITZ; Matlab; MATLAB expm; mftoolbox; JDQZ; JDQR; hlib; testmatrix; UTV; RestoreTools; Netlib; FFTW; SLICOT; Regularization tools; BLAS Cited in: 11 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year A fast solver for linear systems with displacement structure. Zbl 1203.65062Aricò, Antonio; Rodriguez, Giuseppe 2010 all top 5 Cited by 18 Authors 2 Rodriguez, Giuseppe 1 Aricò, Antonio 1 Bini, Dario Andrea 1 Böttcher, Albrecht 1 Byun, Heejung 1 Chesnokov, Andrey A. 1 Fasino, Dario 1 Halwass, Martin 1 Jiang, Zhaolin 1 Kressner, Daniel 1 Liesen, Jörg 1 Luce, Robert 1 Pan, Victor Yakovlevich 1 Poloni, Federico Giovanni 1 Redivo-Zaglia, Michela 1 Van Barel, Marc 1 Zhang, Xing 1 Zheng, Yanpeng Cited in 5 Serials 4 Numerical Algorithms 2 SIAM Journal on Matrix Analysis and Applications 2 Linear Algebra and its Applications 1 Journal of Computational and Applied Mathematics 1 Japan Journal of Industrial and Applied Mathematics all top 5 Cited in 6 Fields 10 Numerical analysis (65-XX) 7 Linear and multilinear algebra; matrix theory (15-XX) 2 Field theory and polynomials (12-XX) 2 Operator theory (47-XX) 1 Probability theory and stochastic processes (60-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year