gyrdym
solve() returns all zeros for an 8x8 system (homography), while custom pivot-based solution works
Description
I'm trying to solve an 8x8 linear system for homography estimation in Dart. When I use the solve() method from ml_linalg, the solution vector is always all zeros, which is incorrect. However, if I use my own pivot-based Gauss elimination function, it yields the correct solution.
What I'm trying to achieve
I want to compute a homography matrix (3x3) using four point correspondences (source → destination). This requires solving an 8x8 system. Here is the high-level approach:
Construct an 8x8 matrix A and an 8x1 vector b. Solve A * x = b for x, which has 8 unknowns (since h22 is fixed to 1). Build the final 3x3 homography matrix using the 8 parameters from x.
What goes wrong
When using ml_linalg's Matrix.solve(), I get a vector of all zeros [0,0,0,0,0,0,0,0]. When using my custom pivot-based Gauss elimination (_solveLinearSystem8), I get the correct (non-zero) homography parameters. I tried switching from dtype: DType.float32 to dtype: DType.float64, but the same problem occurs (the solve() result is still all zeros).
Why I suspect a pivot / numerical stability issue
My custom code does partial pivoting, i.e., it looks for the row with the largest absolute pivot value and swaps rows before eliminating. This typically handles near-singular or poorly conditioned matrices better.
ml_linalg's solve() might not be doing partial pivoting or might have an internal numerical issue with this particular matrix. If the matrix is ill-conditioned, a method without pivoting can collapse to a zero solution.
Example Code:
Matrix4 findHomographyMatrix4(List<Offset> src, List<Offset> dst) {
assert(src.length == 4 && dst.length == 4,
'Hem src hem de dst listeleri 4 nokta içermeli.');
final List<List<double>> a = [];
final List<double> b = [];
for (int i = 0; i < 4; i++) {
final x = src[i].dx;
final y = src[i].dy;
final xp = dst[i].dx;
final yp = dst[i].dy;
a.add([x, y, 1, 0, 0, 0, -x * xp, -y * xp]);
a.add([0, 0, 0, x, y, 1, -x * yp, -y * yp]);
b.add(xp);
b.add(yp);
}
/// Attempting to solve with ml_linalg
/// This returns all zeros for me:
// final bb = b.map((value) => [value]).toList();
// final aMatrix = Matrix.fromList(a, dtype: DType.float64);
// final bMatrix = Matrix.fromList(bb, dtype: DType.float64);
// final xMatrix = aMatrix.solve(bMatrix);
// final x = List.generate(8, (i) => xMatrix.getRow(i)[0]);
/// Using my custom pivot-based code that works:
final x = _solveLinearSystem8(a, b);
final m = Matrix4.zero();
final h00 = x[0];
final h01 = x[1];
final h02 = x[2];
final h10 = x[3];
final h11 = x[4];
final h12 = x[5];
final h20 = x[6];
final h21 = x[7];
final h22 = 1.0;
// Row 0
m.setEntry(0, 0, h00);
m.setEntry(0, 1, h01);
m.setEntry(0, 3, h02);
// Row 1
m.setEntry(1, 0, h10);
m.setEntry(1, 1, h11);
m.setEntry(1, 3, h12);
// Row 2
m.setEntry(2, 2, 1.0);
// Row 3
m.setEntry(3, 0, h20);
m.setEntry(3, 1, h21);
m.setEntry(3, 3, h22);
return m;
}
List<double> _solveLinearSystem8(List<List<double>> A, List<double> b) {
final M = List.generate(8, (r) => List<double>.from(A[r]));
final C = List<double>.from(b);
for (int i = 0; i < 8; i++) {
// Pivot seçimi: en büyük mutlak değer
double maxVal = M[i][i].abs();
int pivot = i;
for (int r = i + 1; r < 8; r++) {
final val = M[r][i].abs();
if (val > maxVal) {
maxVal = val;
pivot = r;
}
}
if (pivot != i) {
final tempRow = M[i];
M[i] = M[pivot];
M[pivot] = tempRow;
final tempVal = C[i];
C[i] = C[pivot];
C[pivot] = tempVal;
}
final diag = M[i][i];
for (int r = i + 1; r < 8; r++) {
final factor = M[r][i] / diag;
for (int c = i; c < 8; c++) {
M[r][c] -= factor * M[i][c];
}
C[r] -= factor * C[i];
}
}
final x = List.filled(8, 0.0);
for (int i = 7; i >= 0; i--) {
double sum = C[i];
for (int c = i + 1; c < 8; c++) {
sum -= M[i][c] * x[c];
}
x[i] = sum / M[i][i];
}
return x;
}
I’d be happy to provide more details, logs, or help debug further if needed.
Hello,
Thank you for creating the issue!
Probably, ml_linalg has numerical stability issues, I need to check it.
@yesilcimenahmet sure, my implementation of 'solve' is quite basic, with no pivoting. Please, give me a couple of days, I'll try to make solve more performant and stable. I'll keep you posted on the progress.
Thank you for your detailed report and patience!
@gyrdym Thank you for maintaining this library. Do you plan to add SVD support in future updates? It’s a critical method for many applications, and its inclusion would be highly appreciated.