Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fast Hessenberg reduction of some rank structured matrices   We develop two fast algorithms for Hessenberg reduction of a structured
matrix $A = D + UV^H$ where $D$ is a real or unitary $n \times n$ diagonal
matrix and $U, V \in\mathbb{C}^{n \times k}$. The proposed algorithm for the
real case exploits a two--stage approach by first reducing the matrix to a
generalized Hessenberg form and then completing the reduction by annihilation
of the unwanted sub-diagonals. It is shown that the novel method requires
$O(n^2k)$ arithmetic operations and it is significantly faster than other
reduction algorithms for rank structured matrices. The method is then extended
to the unitary plus low rank case by using a block analogue of the CMV form of
unitary matrices. It is shown that a block Lanczos-type procedure for the block
tridiagonalization of $\Re(D)$ induces a structured reduction on $A$ in a block
staircase CMV--type shape. Then, we present a numerically stable method for
performing this reduction using unitary transformations and we show how to
generalize the sub-diagonal elimination to this shape, while still being able
to provide a condensed representation for the reduced matrix. In this way the
complexity still remains linear in $k$ and, moreover, the resulting algorithm
can be adapted to deal efficiently with block companion matrices.

7
The categories of this paper are: hep-th
0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
20
The categories of this paper are: acc-phys
18
The categories of this paper are: econ
10
The categories of this paper are: q-bio
8
The categories of this paper are: hep-ex
16
The categories of this paper are: stat
13
The categories of this paper are: quant-ph
29
The categories of this paper are: funct-an
5
The categories of this paper are: gr-qc
17
The categories of this paper are: q-fin
33
The categories of this paper are: plasm-ph
11
The categories of this paper are: hep-lat
28
The categories of this paper are: alg-geom
21
The categories of this paper are: adap-org