A Fast Block-Greedy Algorithm for Quasi-optimal Meshless Trial Subspace Selection

Leevan Ling*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

15 Citations (Scopus)
9 Downloads (Pure)


Meshless collocation methods are often seen as a flexible alternative to overcome difficulties that may occur with other methods. As various meshless collocation methods gain popularity, finding appropriate settings becomes an important open question. Previously, we proposed a series of sequential-greedy algorithms for selecting quasi-optimal meshless trial subspaces that guarantee stable solutions from meshless methods, all of which were designed to solve a more general problem: "Let A be an M × N matrix with full rank M; choose a large M × K submatrix formed by K ≤ M columns of A such that it is numerically of full rank." In this paper, we propose a block-greedy algorithm based on a primal/dual residual criterion. Similar to all algorithms in the series, the block-greedy algorithm can be implemented in a matrix-free fashion to reduce the storage requirement. Most significantly, the proposed algorithm reduces the computational cost from the previous O(K4+NK2) to at most O(NK2). Numerical examples are given to demonstrate how this efficient and ready-to-use approach can benefit the stability and applicability of meshless collocation methods.

Original languageEnglish
Pages (from-to)A1224-A1250
Number of pages27
JournalSIAM Journal on Scientific Computing
Issue number2
Publication statusPublished - 26 Apr 2016

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Adaptive greedy algorithm
  • Basis selection
  • Kansa method
  • Kernel collocation
  • Radial basis function


Dive into the research topics of 'A Fast Block-Greedy Algorithm for Quasi-optimal Meshless Trial Subspace Selection'. Together they form a unique fingerprint.

Cite this