Welcome to NNCAlib’s Documentation!

About \(\texttt{NNCAlib}\):

NNCA (New Nested Cross Approximation) is an \(\mathcal{O}(N)\) complexity algorithm to construct \(\mathcal{H}^{2}\) matrices. \(\texttt{NNCAlib}\) library constructs a H2 matrix representation of a given matrix using NNCA. Further it demonstrates:

1. the performance of the fast \(\mathcal{H}^{2}\) matrix vector product using NNCA in 2D, 3D, and nD

2. the performance of fast kernel based SVM, where the matrix vector products encountered are accelerated using NNCA.

NCA is a technique developed to construct the \(\mathcal{H}^{2}\) matrix approximation of a given matrix arising out of \(N\) body problems. NNCA is a new variant of the Nested Cross Approximation (NCA). NNCA differs from the existing NCAs in the following ways. The existing NCA by Bebendorf et al. is not an analytic method, whereas NNCA is an algebraic method. Another existing NNCA by Zhao et al. is an algebraic method and uses two tree traversals in its algorithm. Whereas NNCA uses a single tree traversal in its algorithm. It has been numerically shown in the NNCA article that NNCA performs computationally better than the existing NCAs.

The code is written in C++ and features an easy-to-use interface.

More about NNCA can be found in the article.

Doc Contents

Contents:

• Installation and Building
  • Downloading the Source
  • Dependencies
  • Installation
  • Testing
• Tutorial
  • Setting Parameters in make file
  • Building and Executing
  • Defining the kernel function
  • Defining location of particles/data points:
  • Defining vector b:
  • Defining vector x:
  • Creating an Instance of AFMMnD:
• Reproducibility
  • Experiment 1: Matrix-vector product with uniform distribution of particles in 2D and its comparison with the existing NCAs
  • Experiment 2: Matrix-vector product with Chebyshev distribution of particles in 2D
  • Experiment 3: Matrix-vector product with a uniform distribution of particles in 3D
  • Experiment 4: Matrix-vector product with Chebyshev distribution of particles in 3D
  • Experiment 5: Integral equation solver in 3D
  • Experiment 6: Kernel SVM in 4D

Other Links

Learn more about \(\texttt{NNCAlib}\) by visiting the

• Code Repository: https://github.com/SAFRAN-LAB/NNCA

• Documentation: https://nnca.readthedocs.io/en/latest/

• Article: https://arxiv.org/pdf/2203.14832.pdf