Accurate solutions of weighted least squares problems associated with rank-structured matrices

Abstract In this paper, we consider how to accurately solve the weighted least squares (WLS) problem associated with a class of rank-structured matrices admitting bidiagonal representations (BRs) from weighted polynomial regression. We develop a new algorithm to solve the structured WLS problem, provided that BRs are available. A mechanism is exploited to guarantee that all the solution components are computed with a desirable high accuracy. Forward error analysis and numerical experiments are performed to confirm the high accuracy. In particular, our random examples demonstrate the high relative accuracy of each computed solution component, independently of the ill-conditioning of weighted matrices.