Time and space efficient generators for quasiseparable matrices. (English) Zbl 1381.65035

Summary: The class of quasiseparable matrices is defined by the property that any submatrix entirely below or above the main diagonal has small rank, namely below a bound called the order of quasiseparability. These matrices arise naturally in solving partial differential equations for particle interaction with the Fast Multi-pole Method, or computing generalized eigenvalues. From these application fields, structured representations and algorithms have been designed in numerical linear algebra to compute with these matrices in time linear in the matrix dimension and either quadratic or cubic in the quasiseparability order. Motivated by the design of the general purpose exact linear algebra library LinBox, and by algorithmic applications in algebraic computing, we adapt existing techniques introduce novel ones to use quasiseparable matrices in exact linear algebra, where sub-cubic matrix arithmetic is available. In particular, we will show, the connection between the notion of quasiseparability and the rank profile matrix invariant, that we have introduced in [J.-G. Dumas et al., in: Proceedings of the 40th international symposium on symbolic and algebraic computation, ISSAC 2015. New York, NY: Association for Computing Machinery (ACM). 149–156 (2015; Zbl 1345.65019)]. It results in two new structured representations, one being a simpler variation on the hierarchically semiseparable storage, and the second one exploiting the generalized Bruhat decomposition. As a consequence, most basic operations, such as computing the quasiseparability orders, applying a vector, a block vector, multiplying two quasiseparable matrices together, inverting a quasiseparable matrix, can be at least as fast and often faster than previous existing algorithms.


65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices


Zbl 1345.65019


Full Text: DOI arXiv


[1] Bini, D.; Pan, V., Polynomial and matrix computations, vol.1: fundamental algorithms, (1994), Birkhäuser Boston · Zbl 0809.65012
[2] Boito, P.; Eidelman, Y.; Gemignani, L., Implicit QR for companion-like pencils, Math. Comput., 85, 300, 1753-1774, (2016) · Zbl 1335.65041
[3] Bostan, A.; Jeannerod, C.-P.; Schost, E., Solving structured linear systems with large displacement rank, Theor. Comput. Sci., 407, 1-3, 155-181, (Nov. 2008)
[4] Bruhat, F., Sur LES représentations induites des groupes de Lie, Bull. Soc. Math. Fr., 84, 97-205, (1956) · Zbl 0074.10303
[5] Carrier, J.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Stat. Comput., 9, 4, 669-686, (Jul. 1988)
[6] Chan, T. F., Rank revealing QR factorizations, Linear Algebra Appl., 88, 67-82, (Apr. 1987)
[7] Chandrasekaran, S.; Dewilde, P.; Gu, M.; Pals, T.; Sun, X.; van der Veen, A.; White, D., Some fast algorithms for sequentially semiseparable representations, SIAM J. Matrix Anal. Appl., 27, 2, 341-364, (Jan. 2005)
[8] Chandrasekaran, S.; Gu, M.; Pals, T., A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl., 28, 3, 603-622, (Jan. 2006)
[9] Chandrasekaran, S.; Ipsen, I., On rank-revealing factorisations, SIAM J. Matrix Anal. Appl., 15, 2, 592-622, (Apr. 1994)
[10] Delvaux, S.; Van Barel, M., A givens-weight representation for rank structured matrices, SIAM J. Matrix Anal. Appl., 29, 4, 1147-1170, (Nov. 2007)
[11] Dumas, J.-G.; Pernet, C.; Sultan, Z., Simultaneous computation of the row and column rank profiles, (Kauers, M., Proc. ISSAC’13, (2013), ACM Press), 181-188 · Zbl 1360.65122
[12] Dumas, J.-G.; Pernet, C.; Sultan, Z., Computing the rank profile matrix, (Proc ISSAC’15, (2015), ACM New York, NY, USA), 149-156, Distinguished paper award · Zbl 1345.65019
[13] Dumas, J.-G.; Pernet, C.; Sultan, Z., Fast computation of the rank profile matrix and the generalized Bruhat decomposition, J. Symb. Comput., (2016)
[14] Eidelman, Y.; Gohberg, I., On a new class of structured matrices, Integral Equ. Oper. Theory, 34, 3, 293-324, (Sep. 1999)
[15] Eidelman, Y.; Gohberg, I., On generators of quasiseparable finite block matrices, Calcolo, 42, 3-4, 187-214, (Dec. 2005)
[16] Eidelman, Y.; Gohberg, I.; Olshevsky, V., The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order, Linear Algebra Appl., 404, 305-324, (2005) · Zbl 1079.65038
[17] Gohberg, I.; Kailath, T.; Koltracht, I., Linear complexity algorithms for semiseparable matrices, Integral Equ. Oper. Theory, 8, 6, 780-804, (Nov. 1985)
[18] Hwang, T.-M.; Lin, W.-W.; Yang, E. K., Rank revealing LU factorizations, Linear Algebra Appl., 175, 115-141, (Oct. 1992)
[19] Jeannerod, C.-P.; Pernet, C.; Storjohann, A., Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, J. Symb. Comput., 56, 46-68, (2013) · Zbl 1329.65065
[20] Kailath, T.; Kung, S.-Y.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 2, 395-407, (Apr. 1979)
[21] Le Gall, F., Powers of tensors and fast matrix multiplication, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. ISSAC ’14, (2014), ACM New York, NY, USA), 296-303 · Zbl 1325.65061
[22] Malaschonok, G. I., Fast generalized Bruhat decomposition, (CASC’10, Lect. Notes Comput. Sci., vol. 6244, (2010), Springer-Verlag Berlin, Heidelberg), 194-202 · Zbl 1290.65038
[23] Manthey, W.; Helmke, U., Bruhat canonical form for linear systems, Linear Algebra Appl., 425, 2-3, 261-282, (2007), Special issue in honor of Paul Fuhrmann · Zbl 1123.93028
[24] Pan, C.-T., On the existence and computation of rank-revealing LU factorizations, Linear Algebra Appl., 316, 1-3, 199-222, (Sep. 2000)
[25] Pan, V., On computations with dense structured matrices, Math. Comput., 55, 191, 179-190, (1990) · Zbl 0703.47022
[26] Pernet, C., Computing with quasiseparable matrices, (Proc. ISSAC’16, (2016), ACM), 389-396, hal-01264131 · Zbl 1360.65128
[27] Sheng, Z.; Dewilde, P.; Chandrasekaran, S., Algorithms to solve hierarchically semi-separable systems, (Alpay, D.; Vinnikov, V., System Theory, the Schur Algorithm and Multidimensional Analysis, Oper. Theory, Adv. Appl., vol. 176, (2007), Birkhäuser Basel), 255-294 · Zbl 1123.65020
[28] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356, (1969) · Zbl 0185.40101
[29] Linbox: linear algebra over black-box matrices, (2016), v1.4.1 edition
[30] Tyrtyshnikov, E., Matrix Bruhat decompositions with a remark on the QR (GR) algorithm, Linear Algebra Appl., 250, 61-68, (1997) · Zbl 0870.65022
[31] Vandebril, R.; Barel, M. V.; Golub, G.; Mastronardi, N., A bibliography on semiseparable matrices, Calcolo, 42, 3, 249-270, (2005) · Zbl 1168.15312
[32] Vandebril, R.; Van Barel, M.; Mastronardi, N., Matrix computations and semiseparable matrices: linear systems, vol. 1, (2007), The Johns Hopkins University Press
[33] Xia, J.; Chandrasekaran, S.; Gu, M.; Li, X. S., Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17, 6, 953-976, (Dec. 2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.