Repository: TheAlgorithms/Java
Pull request #6196 (2025-03-14 18:06:53)

Added a linear system solver
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6196?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `87.09677%` with `4 lines` in your changes missing coverage. Please review.
> Project coverage is 73.80%. Comparing base [(`e6073f8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/e6073f8fefa7f1b63a9170ac56712f04469c5442?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`c90a5ae`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/c90a5aedf2be4c95d83cb0b854d01f63cd44ca97?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6196?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...ain/java/com/thealgorithms/matrix/SolveSystem.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6196?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fmatrix%2FSolveSystem.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9tYXRyaXgvU29sdmVTeXN0ZW0uamF2YQ==) | 87.09% | [2 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6196      +/-   ##
============================================
+ Coverage     73.78%   73.80%   +0.02%     
- Complexity     5219     5227       +8     
============================================
  Files           667      668       +1     
  Lines         17983    18014      +31     
  Branches       3457     3466       +9     
============================================
+ Hits          13269    13296      +27     
- Misses         4196     4198       +2     
- Partials        518      520       +2     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6196?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>🚀 New features to boost your workflow: </summary>

- ❄ [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>
DenizAltunkapan: Looks good to me! 🔥 just tested it with some own matrices.

Patch:
diff --git a/src/main/java/com/thealgorithms/matrix/SolveSystem.java b/src/main/java/com/thealgorithms/matrix/SolveSystem.java
new file mode 100644
index 00000000..9e683bc4
--- /dev/null
+++ b/src/main/java/com/thealgorithms/matrix/SolveSystem.java
@@ -0,0 +1,71 @@
+package com.thealgorithms.matrix;
+
+/**
+ * This class implements an algorithm for solving a system of equations of the form Ax=b using gaussian elimination and back substitution.
+ *
+ * @link <a href="https://en.wikipedia.org/wiki/Gaussian_elimination">Gaussian Elimination Wiki</a>
+ * @see InverseOfMatrix finds the full of inverse of a matrice, but is not required to solve a system.
+ */
+public final class SolveSystem {
+    private SolveSystem() {
+    }
+
+    /**
+     * Problem: Given a matrix A and vector b, solve the linear system Ax = b for the vector x.\
+     * <p>
+     * <b>This OVERWRITES the input matrix to save on memory</b>
+     *
+     * @param matrix    - a square matrix of doubles
+     * @param constants - an array of constant
+     * @return solutions
+     */
+    public static double[] solveSystem(double[][] matrix, double[] constants) {
+        final double tol = 0.00000001; // tolerance for round off
+        for (int k = 0; k < matrix.length - 1; k++) {
+            // find the largest value in column (to avoid zero pivots)
+            double maxVal = Math.abs(matrix[k][k]);
+            int maxIdx = k;
+            for (int j = k + 1; j < matrix.length; j++) {
+                if (Math.abs(matrix[j][k]) > maxVal) {
+                    maxVal = matrix[j][k];
+                    maxIdx = j;
+                }
+            }
+            if (Math.abs(maxVal) < tol) {
+                // hope the matrix works out
+                continue;
+            }
+            // swap rows
+            double[] temp = matrix[k];
+            matrix[k] = matrix[maxIdx];
+            matrix[maxIdx] = temp;
+            double tempConst = constants[k];
+            constants[k] = constants[maxIdx];
+            constants[maxIdx] = tempConst;
+            for (int i = k + 1; i < matrix.length; i++) {
+                // compute multipliers and save them in the column
+                matrix[i][k] /= matrix[k][k];
+                for (int j = k + 1; j < matrix.length; j++) {
+                    matrix[i][j] -= matrix[i][k] * matrix[k][j];
+                }
+                constants[i] -= matrix[i][k] * constants[k];
+            }
+        }
+        // back substitution
+        double[] x = new double[constants.length];
+        System.arraycopy(constants, 0, x, 0, constants.length);
+        for (int i = matrix.length - 1; i >= 0; i--) {
+            double sum = 0;
+            for (int j = i + 1; j < matrix.length; j++) {
+                sum += matrix[i][j] * x[j];
+            }
+            x[i] = constants[i] - sum;
+            if (Math.abs(matrix[i][i]) > tol) {
+                x[i] /= matrix[i][i];
+            } else {
+                throw new IllegalArgumentException("Matrix was found to be singular");
+            }
+        }
+        return x;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/matrix/SolveSystemTest.java b/src/test/java/com/thealgorithms/matrix/SolveSystemTest.java
new file mode 100644
index 00000000..c8d289bd
--- /dev/null
+++ b/src/test/java/com/thealgorithms/matrix/SolveSystemTest.java
@@ -0,0 +1,21 @@
+package com.thealgorithms.matrix;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+class SolveSystemTest {
+
+    @ParameterizedTest
+    @MethodSource({"matrixGenerator"})
+    void solveSystem(double[][] matrix, double[] constants, double[] solution) {
+        double[] expected = SolveSystem.solveSystem(matrix, constants);
+        assertArrayEquals(expected, solution, 1.0E-10, "Solution does not match expected");
+    }
+    private static Stream<Arguments> matrixGenerator() {
+        return Stream.of(Arguments.of(new double[][] {{-5, 8, -4}, {0, 6, 3}, {0, 0, -4}}, new double[] {38, -9, 20}, new double[] {-2, 1, -5}), Arguments.of(new double[][] {{-2, -1, -1}, {3, 4, 1}, {3, 6, 5}}, new double[] {-11, 19, 43}, new double[] {2, 2, 5}));
+    }
+}