The "best way" to order unknowns in linear systems Start with a linear system of the form
\begin{equation*}
Ax + Bt + C = 0,
\end{equation*}
where $x = (x_1, \dots, x_n) \in \mathbb R^n$ is the vector of unknowns, $t \in \mathbb R^m$ is a vector of parameters, $A \in GL(n, \mathbb R)$, $B \in \mathcal M_{n,m}(\mathbb R)$ and $C \in \mathbb R^n$. Suppose you can apply Gauss reduction without pivoting. Then you end up with a system of the form
\begin{equation*}
Ux + Pt + Q = 0,
\end{equation*}
where $U$ is a $n \times n$ unitriangular matrix, $P \in \mathcal M_{n,m}(\mathbb R)$ and $Q \in \mathbb R^n$. This allows to compute $x$ recursively by:
\begin{equation}
\begin{cases}
x_n = -(p_{n1} t_1 + \dots + p_{nm} t_m + q_n) \\
x_{n-1} = -(u_{n-1,n} x_n + p_{n-1,1} t_1 + \dots + p_{n-1,m} t_m + q_{n-1}) \\
\dots \\
x_1 = -(u_{12} x_2 + \dots + u_{1n} x_n + p_{11} t_1 + \dots + p_{1m} t_m + q_1) \\
\end{cases}
\end{equation}
Of course, you can do this for every permutation of $(x_1, \dots, x_n)$, and also for every permutation of rows that does not give you zeroes on the diagonal at some point of Gauss reduction. Now my questions are:

*

*Is it possible to know in advance (i.e. without doing the whole computation) which permutation of rows does not make Gauss reduction fail because of zeroes on the diagonal? I think this is very classical but I did not find any reference.


*Is it possible to know in advance which permutation of rows and columns gives you the triple $(U, P, Q)$ with the greatest number of zeroes? This would give me the best algorithm that computes $x$ from a given $t$.


*Does it help if you make some assumptions on the form of $A$? In my situation $A$ is sparse, often it is also symmetric and weakly diagonally dominant.
Thank you in advance.
 A: (1): the classical condition is that all leading principal submatrices of $A$ (apart from $A$ itself) are nonsingular; see e.g. Theorem 5.2.3.4 here. This applies because what you are computing is an LU factorization of $A$ (I see you don't use this term; if it is not familiar to you, I suggest you start from reading about it, because it is a very useful concept for this kind of problems.) This condition might settle some special cases, but in general as far as I know there is no better way to tell if the leading principal matrices are singular than computing the factorization and seeing if it succeeds.
(2) Optimally, no. Even with $P=Q=0$ and $A$ positive-definite, computing the minimum fill-in is NP-complete. There are various heuristics though, e.g. this, because it is a common problem in numerical linear algebra. Basically every sparse LU package contains such a heuristic, so normally as an end-user you don't have to worry about that.
(3) Not really, as stated in (2). Usually you worry about fill-in only for sparse matrices to begin with, and even for positive definite matrices (which are diagonally dominant up to a scaling that does not affect sparsity) the NP-completeness result holds.
Addendum: I don't think that this is going to give you the best algorithm to compute $x$ given a $t$, as you claim in (2). Rather, I would, given a $t$, (a) evaluate $Bt+C$ to a parameterless matrix (b) apply to it the inverses of the elimination matrix $L$ and $U$ obtained by Gaussian elimination. In this way, you can disregard sparsity in $P,Q$ and focus on reducing fill-in in $U$ only.
