Neural Acceleration for Incomplete Factorization Preconditioning

Incomplete Cholesky, are black box methods that are typically used to generate these preconditioners. These methods normally require trying techniques such as scaling, shifting, and identifying fill-in to achieve the desired reduction in iterations. However, the algorithm of incomplete factorization tends to be difficult to parallelize due to the low computational intensity. [pg. 2]

Traditional NN method for solving linear system try computing inverse but that is error prone.

Many traditional neural network-inspired approaches try to construct a precon- ditioner M such that \(M \approx A^{-1}\). In particular, the network itself becomes the output. However, constructing an inverse directly is an error-prone task. [pg. 6]

• Construct a NN that has a hidden layer such that it computes \(Ax\) in the form of \(LL^Tx\)
• Sample some \(x\) and \(y\) then train the parameters of NN that represent \(L\)
• The obtained \(L\) is the preconditioner

The neural acceleration method could take in the sparse matrix A and generate samples X and Y in order to train L. In our experimental results, we √ demonstrate that the number of samples needed is relatively small (i.e., N where N = dimension(A)). For the output, the method could either output L to be used by the problem in its iterative solver package or function pointers to apply sparse triangular solve for this on the GPU where it was generated. [pg. 7]

• Preconditioner in the form of \(L\) is common technique

Limiting the nonzero pattern of the preconditioner to that of the nonzero pattern of the input matrix is commonly done in many traditional preconditioner methods. Therefore, we do not perceive this as a major limitation as many traditional methods also use it [pg. 7]

• Depends on number of iterations and optimization algorithm

The training cost would depend on both the numerical optimization method used and the number of iterations needed to construct a good approximation. [pg. 8]

• We use AdaGrad

AdaGrad is commonly used for training deep learning models with sparse gradients [pg. 9]

• We sample X from random distribution [pg. 9]

  • Question 1:

    Effect of different Network Initialization and Different Sparse Matrices (with different range of entries)

    E.g. He, Uniform, …

  • Question 2:

    Effect of sampling X from different distribution?

    Normalization is tried in this paper. I don't have other suggestion. Were other distribution tried? Uniform, Normal, …

    Probably didn't matter.

Even with a sparse matrix that is not full rank, the image remains difficult to see after 25 samples and the error is very high (i.e., > 1). Therefore, the number of samples should be ≤ N to be a successful method. pg. 9

Number of samples should be <= N or ~ N ?

• We construct a NN of the form \(LU\)
• We avoid permutation similar to other ILU code

We avoid the permutation in a similar manner as many other ILU codes by trying to permute large values to the diagonal first and excluding matrices that fail due to stability along the way [pg. 9]

• We use two variety of X:
  • randomly selected X, not normalized (NN) and
  • randomly selected X, normalized (NNN) [Page 12]
• Not normalized X (i.e. NN) do better

one set of randomly selected X with normalized samples (denoted as NNN)

NN generally does better than NNN. This is a nice finding for two particular reasons. First, normal- ization does not need to be done, thus saving time in training. Second, the training of NN is much less sensitive. In particular, a simple parameter of α = 0.1 works well with AdaGrad for training, while the training of NNN is much more difficult. [pg. 16]

• ILU is better preconditioner but failes to converge in some cases

The \(LL^T\) model tends to be a better choice than the LU model for most of the test suite, even for matrices that are non-symmetric. [Page 20]

• \(LU\) isn't good when the matrix is SPD [Page 20]
• But \(LL^T\) is good in both cases

A total of \(\sqrt N\) training vectors were generated, and the models were trained iteratively utilizing a batch of 1 vector per iteration for all LLT models. [pg. 12]

In Neural Acceleration of Graph Based Utility Functions for Sparse Matrices paper, the NN was computed at compile time. But here it is done in run time.

How is Neural Acceleration defined? No compiler tricks or compile time computing is utilized in this case.

So, is this neural acceleration? (only when the matrix to factorize is available at compile time can we compute the preconditioner at compile time)

• Certain orderings (ND, RCM), are known to reduce fill-in.

The amount of fill-in during factorization is a factor of the nonzero pattern. Certain orderings, e.g., nested-dissection (ND) [11] and reverse Cuthill-McKee (RCM) [12], are known to reduce fill-in. In theory, the reduction in fill-in should result in better preconditioners. [pg. 4]

Typo: factor or the nonzero -> factor of the nonzero

• And reduction in fill in should reduce factorization time, but not always (AMD).

While this idea holds in general, it does not hold for all orderings. An example of this is approximate minimal degree (AMD) ordering which reduces fill-in but may not reduce iteration count to the same degree as RCM [pg. 4]