A FAST MEMORY EFFICIENT CONSTRUCTION ALGORITHM FOR HIERARCHICALLY SEMI-SEPARABLE REPRESENTATIONS

作者：Lessel K^*; Hartman M^*; Chandrasekaran S^*

来源：SIAM Journal on Matrix Analysis and Applications, 2016, 37(1): 338-353.

DOI：10.1137/15M1028467

• fast multipole method
• hierarchically semi-separable representations
• fast algorithms
• orthogonal factorizations
• low-rank structures
• memory efficient

Existing hierarchically semi-separable construction algorithms for dense n x n matrices require as much as O(n(2)) peak workspace memory, at a cost of O(n(2)) flops. An algorithm is presented which requires O(n(1.5)) peak worskpace memory in the worst case, while still requiring only O(n(2)) flops.

• 出版日期2016