Timeline for Solving linear system of nonhomogenous equations that are known to have natural solutions
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 19, 2020 at 15:08 | comment | added | altugkarakurt | While checking the combination, you’re only checking if the entries of a candidate solution are in the feasible intervals. So it takes $2n$ operations. On the other hand, the naive brute-force search plugs it in the system and checks whether equalities hold, which is still polynomial, but costlier than the former option. The gain in the example is the smallest because $z_k$ are close, but if the difference is large, many cases are reduced from plugging-in to feasibility check. I don’t think the latter cost can be avoided for each combination anyway | |
| Jun 19, 2020 at 11:36 | comment | added | Albert Hendriks | The crux seems to be that the list for $z_1=3, z_2=2,\ldots$ is missing: $(1,2,\ldots)$, which is allowed because it's covered by $(2,1,\ldots)$ when permuting the variables (right?). I don't see how that adds value. In the end you're still trying all combination of variable values (i.e. brute-forcing), but only in the context of their upper bounds and using some bounds in the context of already branched variables. I'm sure OP already thought of such bounds. | |
| Jun 19, 2020 at 6:30 | comment | added | altugkarakurt | My bad for assuming the existence of unique solutions. Hopefully the edited answer helps with underdetermined systems. | |
| Jun 19, 2020 at 6:29 | history | edited | altugkarakurt | CC BY-SA 4.0 |
added 1454 characters in body
|
| Jun 19, 2020 at 4:42 | comment | added | Koko191 | I used RREF to try and solve my systems before but it is not guaranteed to return a row with a single coefficient. For example, my system can be very simple like $x_1+x_2+x_3=2$, which is guaranteed to have a few solutions (1-1-0, 1-0-1, 0-1-1) but obviously this system cannot be reduced since there is only one equation in the system. Usually my systems have a few dozen equations but this is to give a sense why REF might not work for me. | |
| Jun 19, 2020 at 0:41 | history | answered | altugkarakurt | CC BY-SA 4.0 |