Better diagnostics for over- and under-determined systems

[Francesco Casella]

Consider the following (trivial) case

model M1
  Real x, y, z;
equation
  x + y = 2;
  x - y = 10;
end M1;

In this case, we already get some useful diagnostics:

[1] 18:15:27 Symbolic Error
Too few equations, under-determined system. The model has 2 equation(s) and 3 variable(s).

[2] 18:15:27 Symbolic Warning
[MM: 2:3-2:15]: Variable z does not have any remaining equation
to be solved in.
  The original equations were:

However, consider this slightly less trivial case

model M2
  Real x, y, z;
  Real a, b, c;
equation
  x + y = 1;
  y + z = -3;
  a + b + c = 4;
  a - c = 2;
  b + c = 4;
end M2;

Here, we currently get

[1] 18:20:06 Symbolic Error
Too few equations, under-determined system. 
The model has 5 equation(s) and 6 variable(s).

In this simple case, inspection shows that a, b, and c are fully determined, while there is a missing equation involving at least one variable in the set {x, y, z} . If you have a much larger number of equations and variables, this kind of intel could be precious to find out where the problem is.

Another interesting case is the following one:

model M3
  Real x, y, z;
  Real a, b, c;
equation
  x + z = 0;
  x + z = 2;
  x + y + z = 0;
  a + b + c = 4;
  a - c = 2;
  b + c = 4;
end M3;

Currently we get (with -d=bltdump):

[2] 18:27:51 Translation Error
Internal error IndexReduction.pantelidesIndexReduction failed! Found empty set of continuous equations. Use -d=bltdump to get more information.

[3] 18:27:51 Symbolic Error
[M3: 6:3-6:12]: Model is structurally singular, error found sorting equations
  1: 0.0 = 2.0
for variables
  1: x:VARIABLE() M3 type: Real

This seems somehow to hint that there is some problem related to variable x, but this information doesn't help much. Better diagnostics should point out the fact that the first two equations are inconsistent, and on the other hand there is not enough information to resolve the ambiguity between x and y

I wonder if we could make good use of linear algebra to do this, beyond structural analysis. The SVD analysis of the Jacobian of the system of equations would easily allow to identify the culprits of the singularity. If J = U*S*V', the non-zero elements of each columns of U that correspond to the zero (or near-zero) singular values in S indicate a set of equations involved in a singularity, and the nonzero elements of the columns of V indicate a set of variables involved in the singularity.

The only problem I see is that we should actually evaluate that Jacobian numerically at an early stage of the backend.