## 3 High-Performance LU Decomposition  
### Partial Refactorisation Concept  
In the following, we explain the concept of partial refactorisation, which was chosen in this work to improve the computation time of the refactorisation step. To begin with, having an LU factorisation, one can utilise it to determine the column dependencies in the _left-looking_ factorisation algorithm. The factorisation algorithm is called left-looking, since it computes the LU decomposition column-wise from left to right. That is, it reads the data of the **LU** matrix computed in prior iterations, which are stored in the columns to the left of the current column. Here and throughout the entire paper, we refer to the **LU** matrix as the single matrix that stores the nonzero entries of the **L** and **U** matrices in a combined manner and which is equal to \(\mathbf{L}-\mathbf{I}+\mathbf{U}\). The main idea is that if one knows the column dependencies of the **LU** matrix, any subsequent refactorisation can be expressed as a factorisation of a subset of the **LU** columns. This was discussed by [PERSON], [PERSON] and [PERSON] [12; 13] and is referred to as the factorisation path algorithm. The algorithm was adopted in this study for partial refactorisation and is described in more detail in the following. The factorisation path algorithm stems from a symbolic view of the LU factorisation procedure, i.e., only considering the nonzero entries but not their numerical values. In each iteration \(k\), the \(k\)-th column of \(A\), denoted in the following as \(\mathbf{a_{k}}\), is factorised and stored in the \(\mathbf{LU}\) matrix. The \(k\)-th column factorisation depends on \(\mathbf{a_{k}}\) and the factorised columns \(\mathbf{y_{j}}\), with \(j<k\), computed prior to iteration \(k\), which have been stored in the \(\mathbf{LU}\) matrix. In order to track how numerical variations in the original matrix affect the factorisation, the values in the \(\mathbf{LU}\) matrix that depend on these varying entries need to be identified. If any value of \(\mathbf{a_{k}}\) changes, it affects the corresponding column \(\mathbf{y_{k}}\) in the \(\mathbf{LU}\) matrix and all subsequent columns to the right that depend on it. Since the left-looking algorithm treats entries above the diagonal, i.e., entries having a row index \(i\) with \(i<k\), differently to those below it, one has to take into account the exact position of a changing entry when computing the factorisation path. First, an example is presented to illustrate the factorisation path computation. In Figure 3, one can see a sample pattern of an \(\mathbf{L}\) matrix. The decomposition here is assumed to be performed without permutations and to be symmetric, i.e., \(\mathbf{U}=\mathbf{L}^{T}\), for simplicity. Further, we assume that the entries in \((2,2)\) and \((4,4)\) of the original matrix have been changed. Starting from the first changed entry \((2,2)\) in the \(\mathbf{L}\) matrix, one finds the closest off-diagonal entry, which is \((6,2)\). Since the value is below the diagonal, the next loop iteration starts at the corresponding diagonal entry \((6,6)\). This procedure is repeated until reaching either the end of the matrix or an entry that is already part of the path. After the first search loop for the initial column \(2\), the factorisation path is \(\{2,6,8,9\}\), consisting of all columns that have been found so far and need to be refactorised. Next, the main loop has to be repeated for the second changed entry \((4,4)\). The affected entries are denoted in green. This time, only columns \(4\) and \(5\) are added to the path, since \(8\) and its subsequent columns are already in the path. The final factorisation path is \(\{4,5,2,6,8,9\}\). In the following, the underlying algorithm is described in its general form. For any numerically varied entry \((i,j)\) in the original matrix, one has to determine its corresponding entry \((\hat{i},\hat{j})\) in the permuted \(\mathbf{LU}\) matrix. In NICSLU, those permutations originate from AMD, MC64 and partial pivoting.