/sci/ - Science & Math » Thread #13258921

9KiB, 281x156, gaussian-elimination.gif

View Same Google iqdb SauceNAO

Anonymous Wed 09 Jun 23:33:39 2021 No.13258921 View Reply Original Report

Quoted By:

I have a problem...

I have a set of linear equations over mod 2. I have many more variables than equations, but I know how many of the variables are =1 mod 2 and =0 mod 2. Can someone tell me how to solve this?

I assume as with all problems like this the first step is likely to row reduce the matrix. But how to incorporate the knowledge of how many variables are 1/0 mod 2? The number of variables and equations is quite large so even trial and error is infeasible. This isn't a question for school so I don't even have a textbook I can use to study a problem like this. If anyone has even a textbook suggestion, I will read it front to back to understand how to solve the problem.

Anonymous

Anonymous Wed 09 Jun 2021 23:37:38 No.13258937 Report

Quoted By: >>13258962

give us some context. why are you interested in this problem.

one thing that immediately comes to mind is that certain modular arithmetics form finite fields. vectorspaces are taken over fields, so conceptually a lot of the stuff you know about linear algebra carries over transparently

Anonymous

Anonymous Wed 09 Jun 2021 23:42:15 No.13258962 Report

Quoted By: >>13258972 >>13258989

>>13258937
I'm really sorry but the problem is part of a personal project that I can't divulge.

I've tried reviewing my linear algebra text from college but interestingly it doesn't even mention solving systems over finite fields (according to the glossary/index/table of contents).

From reading online I am able to see that systems like this can be solved by row reduction if you have enough equations. But that's my main problem. I have far too few equations but I have the addition of knowing the number of 1/0 values to compensate. I also know there is one unique solution to the problem.

Anonymous

Anonymous Wed 09 Jun 2021 23:44:21 No.13258972 Report

Quoted By: >>13259013

>>13258962
What do you mean if you have enough equations? Gaussian elimination works for any number of equations in any number of variables

Anonymous

Anonymous Wed 09 Jun 2021 23:48:02 No.13258989 Report

Quoted By: >>13259017

>>13258962
>knowing the number of 1/0 values to compensate
this might not help you much. enforcing sparsity on the (least squares) solution of a general linear system is equivalent to L0 regularization, which is known to be NP-hard

Anonymous

Anonymous Wed 09 Jun 2021 23:54:31 No.13259013 Report

Quoted By:

>>13258972
For example, if you have 3 variables and 2 equations, you have a 3D space where each equation represents a plane in the 3D space. Row reduction will not tell you a unique solution because there are infinitely many solutions. The intersection of the two planes is a line through the 3D space representing the infinite solutions. However, if I told you the line intersects only one point that is a prime in each dimension, then there is one solution to the problem that isn't represented by the row reduction.

Anonymous

Anonymous Wed 09 Jun 2021 23:56:13 No.13259017 Report

Quoted By: >>13259029

>>13258989
Thank you for your contribution. I'll start reading about L0 regularization and least squares solution. Very sorry to hear it is NP-Hard.

Anonymous

Anonymous Wed 09 Jun 2021 23:59:31 No.13259029 Report

Quoted By: >>13259058

>>13259017
i don't know, though. that applies to finding a solution vector to a least squares problem. usually you have your matrix in hand and don't worry about manipulating it directly when you are trying to solve really really large linear systems.

Anonymous

Anonymous Thu 10 Jun 2021 00:08:33 No.13259058 Report

Quoted By: >>13259206

>>13259029
>usually you have your matrix in hand and don't worry about manipulating it directly when you are trying to solve really really large linear systems

Good to know. Can you give an example?

Anonymous

Anonymous Thu 10 Jun 2021 00:56:26 No.13259206 Report

Quoted By: >>13259243

>>13259058
inverse matrices are almost never computed for very large systems. instead you use iterative methods, which in general only require the ability to apply a matrix and it's adjoint (conjugate transpose).

given an arbitrary linear system Ax = b, suppose you want to compute x. this is usually ill-posed and there are zero or infinite solutions. so one formulates the least squares problem with regularization. if you use L2 regularization, the least squares equation looks something like [A^H A + gamma I] x = A^H b, or more concisely A' x = b'. this modified system is positive definite and conjugate symmetric, so invertible. A' is not usually copmuted in practice; instead you apply the constituent matrices in turn which have the affect of multiplication by A'.

given an invertible A', you can create interative solvers with much better complexity than Gauss-Jordon elimination which takes O(n^3) time. with a positive-definite conjugate-symmetric matrix you can formulate gradient-based solvers like gradient descent or the superior conjugate gradient. if your system lacks the needed properties, you can still solve the problem with things like GMRES.

all of these methods never explicitly compute an inverse to the linear system they are solving, and actually they solve their systems by applying the forward problem over and over again.

Anonymous

Anonymous Thu 10 Jun 2021 01:08:34 No.13259243 Report

Quoted By:

>>13259206
Very, very good information. Thank you. In truth the size of the matrix is huge but even O(n^3) is acceptable if I could guarantee finding the solution. I'll start reading up on the things you've mentioned.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches