Fast approximate computations with Cauchy matrices and polynomials

“refer the reader to [DV98], [EGH13], [MRT05], [CDG06], [CGS07], [VVM], [X12], [XXG12], [X13], [XXCB14], [B10], [BY13], [GR87], [DGR96], [CGR98], and the bibliography therein on FMM and HSS matrices.”

“For efficient alternative techniques, some of which use randomization or heuristics; see [GOS08], [GT01], [HMT11], [LWMRT], [M11], [M11a], [PQY15], [T00], [W14], [XXG12], and the references therein.”

“Lemma 6.1 (See [R85] and [CGS07, equation (2.8)] or [Pb]) .”

“Section 9] extends the algebraic techniques of transformation of matrix structure of [P90] and combines them with the FMM/HSS techniques of this paper (extending the ones of [GKK85], [DV98], [EG99], [H99], [T00], [BH02], [BGH03], [MRT05], [CDG06], [CGS07], [B09], [B10], [VVM], [EGH13], [X12], [XXG12], [X13], [XXCB14],…”

“For efficient alternative techniques, some of which use randomization or heuristics, see [GOS08], [GT01], [HMT11], [LWMRT], [M11], [M11a], [PQY15], [T00], [W14], [XXG12], and the references therein.”

“ution of Problems 2 and 3, respectively, and equation (3.7) of the present subsection extends this bound to Problem 4. For mnthe bound is within a factor of log(n)log(log(n)) from the optimum [S73], [B-O83], [BM75]. The cited algorithms supporting this bound require extended precision of computing and fail already for…”

“We refer the reader to [B68/70], [BP94, Problem 1.”

“unded (e.g., double) precision of computing rules out using the cited fast algorithms, and the known double precision algorithms for Problems 1{4 require quadratic arithmetic time (cf. [BF00], [P64], [BP70], [BEGO08]). This pessimistic outcome, however, does not apply to the important special case where the knots s i…”

“4], where the matrices U and V are unitary, is diagonal, and L and R are triangular (cf. [GL13, Section 5.6.8]). For ecient alternative techniques, some of which use randomization or heuristics, see [GOS08], [GT01], [HMT11], [LWMRT], [M11], [M11a], [PQY15], [T00], [W14], [XXG12], and the references therein. 2.3 Small-…”

“torically HSS representation is just a special case of the representations commonly exploited in the FMM literature" [CDG06]. We refer the reader to the papers and books [GKK85], [DV98], [EG97], [EG99], [H99], [T00], [BH02], [BGH03], Some results of this paper have been presented at ILAS’2013, Providence, RI, 201…”

“Then [GKO95] continued by exploiting the invariance of the Cauchy structure in row interchange, while the other four papers apply the numerically stable FMM in order to operate efficiently with HSS approximations of the basic Cauchy matrix.”

“1 “Historically HSS representation is just a special case of the representations commonly exploited in the FMM literature” [CDG06].”

“Our Section 7.1 and the papers [P15] and [Pa16] cover some extensions of our techniques and results to computations with other structured matrices and rational functions.”

“The closest neighbors of our present study are the papers [MRT05], [CGS07], [XXG12], [XXCB14], and [P15].”

“\FMM" for \Hierarchically Semiseparable" and \Fast Multipole Method". 1 arXiv:1506.02285v2 [math.NA] 7 Apr 2016 [MRT05], [CDG06], [CGS07], [B09], [B10], [VVM], [EGH13], [X12], [XXG12], [X13], [XXCB14], [BY13], [GR87], [DGR96], [CGR88], and the bibliography therein on the FMM and HSS matrices. Our result…”

“The papers [MRT05], [CGS07], [XXG12], and [XXCB14] combine the FMM/HSS techniques with the transformation of matrix structures (traced back to [P90]) in order to devise fast algorithms that approximate the solution of Toeplitz, Hankel, Toeplitz-like, and Hankel-like linear systems of equations by using nearly linear n…”

“The algorithms of [DV98], [EG02] supporting the theorem as well as the study in [CGS07], [VVM], [XXG12], and [EGH13] rely on the representation of (l, u)-quasiseparable matrices with quasiseparable generators, demonstrated by the following 4× 4 example and defined in Theorem 4.”

“the latter matrix.1 \Historically HSS representation is just a special case of the representations commonly exploited in the FMM literature" [CDG06]. We refer the reader to the papers and books [GKK85], [DV98], [EG97], [EG99], [H99], [T00], [BH02], [BGH03], Some results of this paper have been presented at ILAS’2…”

“perations, but the algorithm of [MB72] solves Problem 1 by using O((m+ n)log2(n)log(log(n))) arithmetic operations over any eld of constants. (The algorithm relies on recursive polynomial division of [F72] and FFT-based polynomial division of [S72].) The algorithms of [H72] and [GGS87] have extended the complexity bou…”

“Short Section 9.2 of [PRT92] has pointed out some potential benefits of combining FMM with the algorithm of the paper [G88], but has not developed that idea.”

“One can implement our algorithms by computing the centers c q and the admissible blocks N q of bounded ranks in the merging process, but can avoid a large part of the computations by following the recipe of the papers [CGS07], [X12], [XXG12], and [XXCB14].”

“x.1 \Historically HSS representation is just a special case of the representations commonly exploited in the FMM literature" [CDG06]. We refer the reader to the papers and books [GKK85], [DV98], [EG97], [EG99], [H99], [T00], [BH02], [BGH03], Some results of this paper have been presented at ILAS’2013, Providence,…”

“uires computations with high precision for the worst case input, and the problem is aggravated in the recursive fan-in processes of polynomial multiplication and division in the algorithms of [MB72], [H72], and [GGS87]. Moreover, the following argument demonstrates that we must add at least nbits of precision when the…”

“Furthermore the competing fast algorithms for polynomial and rational interpolation and multipoint evaluation of [MB72], [H72], and [GGS87] have not been cited.”

“sing bounded (e.g., double) precision of computing rules out using the cited fast algorithms, and the known double precision algorithms for Problems 1{4 require quadratic arithmetic time (cf. [BF00], [P64], [BP70], [BEGO08]). This pessimistic outcome, however, does not apply to the important special case where the kno…”

“ers [PSLT93] and [PZHY97] have extended these techniques to the acceleration of multipoint polynomial evaluation, but have not invoked the FMM and achieved only limited progress. Short Section 9.2 of [PRT92] has pointed out some potential benets of combining FMM with the algorithm of the paper [G88], but has not devel…”

“The papers [P95] and [DGR96] applied FMM and some other advanced techniques in order to accelerate approximate polynomial evaluation at a set of real points.”

“…LSTM performed better than (or at least nearly as good as) S4 in many of the tests (except maybe some of the results in Figure 2 and 3), which indicates LSTM, an old but effective architecture, is as promising as the S4 model in de novo molecule design until further analyses indicate otherwise.”

“The DVM algorithm in [17] extends the results in [12], [13], [23] utilizing complex nodes without using displacement equations as in [7], [8], [14].”

“The DVM algorithm in [26] extends the results in [21], [22], [42] utilizing complex nodes without considering quasiseparability and displacement equations as in [12], [13], [23].”

“The DVM factorizations in [5], [10] do not utilize either quasiseparability and displacement equations as in [14], [15], [16], or a O ( N 3 ) algorithm to compute the SVD of polynomial Vandermonde matrices as in [17].”

“…uses nearly linear arithmetic time, and [13] proved that this algorithm supports multipoint polynomial evaluation at a low Boolean cost as well (see also J. van der Hoeven (2008) [33], Pan and Tsigaridas (2013a,b) [28], [29], Kobel and Sagraloff (2013) [14], Pan (2015) [26], and Pan (2015a) [27]).”

“The algorithm works with the equivalent representation of Problem PoEval as the task of multiplication of a Vandermonde matrix V by a vector and equally well applies to the same task for a transposed Vandermonde matrix and matrices with the structures of Vandermonde and Cauchy types (see the papers [122] and [123] for…”

“Computing with Cauchy matrices is an extremely well-studied problem in numerical analysis, with both fast arithmetic and numerical algorithms based on the famous Fast Multipole Method (FMM) [29, 30, 31].”