The MATLAB toolbox Rank Structured Hessenberg Reduction, is hosted on GitHub. You can easily use it from MATLAB decompressing it and adding it to the current path by:
>> addpath rshr-toolbox/matlab
In order to test the fast reduction you can use the provided interfaces. They are called dlr for diagonal plus low rank, and ulr for unitary plus low rank. As an example, for an example of size $128 \times 128$ which is a real diagonal matrix plus a rank $8$ correction:
>> [D, U, V] = rshr_build_example(128, 8, 'dlr');
>> compressedH = rshr_dlr(D, U, V)
compressedH =
struct with fields:
structure: 'dlr'
U: [128×8 double]
V: [128×8 double]
dd: [128×1 double]
ss: [127×1 double]
>> H = rshr_full(compressedH); The same can be done by replacing dlr with url for the unitary plus low rank case. Notice that compressedH is a struct containing the parameters defining H, and only requires $\mathcal O(nk)$ storage. rshr_full is provided for convenience, and builds the full matrix H.
Note: The first time that you run rshr_dlr it builds the MEX files used to call the FORTRAN code to perform the reduction. You need to have MEX correctly configured on your machine to use it. The toolbox is not compatible with GNU Octave yet, but it will be in a future update. The toolbox is also compatible with GNU Octave.
Please report any bug to leonardo.robol@cs.kuleuven.be.