Processing...

### Computing with quasiseparable matrices

**2016-02-03**

1602.01246 | cs.SC

The class of quasiseparable matrices is defined by a pair of bounds, called
the quasiseparable orders, on the ranks of the maximal sub-matrices entirely
located in their strictly lower and upper triangular parts. These arise
naturally in applications, as e.g. the inverse of band matrices, and are widely
used for they admit structured representations allowing to compute with them in
time linear in the dimension and quadratic with the quasiseparable order. We
show, in this paper, the connection between the notion of quasisepa-rability
and the rank profile matrix invariant, presented in [Dumas \& al. ISSAC'15].
This allows us to propose an algorithm computing the quasiseparable orders (rL,
rU) in time O(n^2 s^($\omega$--2)) where s = max(rL, rU) and $\omega$ the
exponent of matrix multiplication. We then present two new structured
representations, a binary tree of PLUQ decompositions, and the Bruhat
generator, using respectively O(ns log n/s) and O(ns) field elements instead of
O(ns^2) for the previously known generators. We present algorithms computing
these representations in time O(n^2 s^($\omega$--2)). These representations
allow a matrix-vector product in time linear in the size of their
representation. Lastly we show how to multiply two such structured matrices in
time O(n^2 s^($\omega$--2)).

**Login to like/save this paper, take notes and configure your recommendations**