Martin Tang Martin Tang - 3 months ago 31
Scala Question

How to solve the homogeneous system of linear equation with Breeze

I try to solve the homogeneous system of linear equation with Breeze.

Ax=0

I want to get a nontrivial solution

However, I got some problems on finding the nontrivial solution

What should I do?

Thanks

This is my code:

val A =DenseMatrix(
(1.0,2.0,3.0,2.0),
(1.0,3.0,5.0,5.0),
(2.0,4.0,7.0,1.0),
(-1.0,-2.0,-6.0,-7.0)
)

val e = DenseVector(0,0,0,0)

val x = A \ e


The error:

breeze.linalg.MatrixSingularException:
at breeze.linalg.operators.DenseMatrixMultiplyStuff$implOpSolveMatrixBy_DMD_DMD_eq_DMD$.LUSolve(DenseMatrixOps.scala:151)
at breeze.linalg.operators.DenseMatrixMultiplyStuff$implOpSolveMatrixBy_DMD_DMD_eq_DMD$.apply(DenseMatrixOps.scala:127)
at breeze.linalg.operators.DenseMatrixMultiplyStuff$implOpSolveMatrixBy_DMD_DMD_eq_DMD$.apply(DenseMatrixOps.scala:115)
at breeze.linalg.ImmutableNumericOps$class.$bslash(NumericOps.scala:144)
at breeze.linalg.DenseMatrix.$bslash(DenseMatrix.scala:53)
at breeze.linalg.operators.DenseMatrixMultiplyStuff$implOpSolveMatrixBy_DMD_DVD_eq_DVD$.apply(DenseMatrixOps.scala:221)
at breeze.linalg.operators.DenseMatrixMultiplyStuff$implOpSolveMatrixBy_DMD_DVD_eq_DVD$.apply(DenseMatrixOps.scala:218)
at breeze.linalg.ImmutableNumericOps$class.$bslash(NumericOps.scala:144)
at breeze.linalg.DenseMatrix.$bslash(DenseMatrix.scala:53)
at .<init>(<console>:27)
at .<clinit>(<console>)
at .<init>(<console>:7)
at .<clinit>(<console>)
at $print(<console>)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:734)
at scala.tools.nsc.interpreter.IMain$Request.loadAndRun(IMain.scala:983)
at scala.tools.nsc.interpreter.IMain.loadAndRunReq$1(IMain.scala:573)
at scala.tools.nsc.interpreter.IMain.interpret(IMain.scala:604)
at scala.tools.nsc.interpreter.IMain.interpret(IMain.scala:568)
at scala.tools.nsc.interpreter.ILoop.reallyInterpret$1(ILoop.scala:760)
at scala.tools.nsc.interpreter.ILoop.interpretStartingWith(ILoop.scala:805)
at scala.tools.nsc.interpreter.ILoop.command(ILoop.scala:717)
at scala.tools.nsc.interpreter.ILoop.processLine$1(ILoop.scala:581)
at scala.tools.nsc.interpreter.ILoop.innerLoop$1(ILoop.scala:588)
at scala.tools.nsc.interpreter.ILoop.loop(ILoop.scala:591)
at scala.tools.nsc.interpreter.ILoop$$anonfun$process$1.apply$mcZ$sp(ILoop.scala:882)
at scala.tools.nsc.interpreter.ILoop$$anonfun$process$1.apply(ILoop.scala:837)
at scala.tools.nsc.interpreter.ILoop$$anonfun$process$1.apply(ILoop.scala:837)
at scala.tools.nsc.util.ScalaClassLoader$.savingContextLoader(ScalaClassLoader.scala:135)
at scala.tools.nsc.interpreter.ILoop.process(ILoop.scala:837)
at scala.tools.nsc.interpreter.ILoop.main(ILoop.scala:904)
at org.jetbrains.plugins.scala.compiler.rt.ConsoleRunner.main(ConsoleRunner.java:64)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)

Answer

First of all, your code does not produce this error , but a type Error because your vector is of [Int] . Do try to run the code you post before posting it.
Second, your matrix has non zero determinant, so there is no such solution.
You can see that easily with breeze

scala> import breeze.linalg._
import breeze.linalg._

scala>   val A =DenseMatrix(
     |     (1.0,2.0,3.0,2.0),
     |     (1.0,3.0,5.0,5.0),
     |     (2.0,4.0,7.0,1.0),
     |     (-1.0,-2.0,-6.0,-7.0)
     |     )
A: breeze.linalg.DenseMatrix[Double] =
1.0   2.0   3.0   2.0
1.0   3.0   5.0   5.0
2.0   4.0   7.0   1.0
-1.0  -2.0  -6.0  -7.0
scala> det(A)
res6: Double = -14.0

We can change one row so that they become linearly-dependent

scala> val nl = DenseVector(1,2,-1,0.0).t * A
ago 19, 2016 6:47:22 PM com.github.fommil.netlib.BLAS <clinit>
WARNING: Failed to load implementation from: com.github.fommil.netlib.NativeSystemBLAS
ago 19, 2016 6:47:22 PM com.github.fommil.netlib.BLAS <clinit>
WARNING: Failed to load implementation from: com.github.fommil.netlib.NativeRefBLAS
nl: breeze.linalg.Transpose[breeze.linalg.DenseVector[Double]] = Transpose(DenseVector(1.0, 4.0, 6.0, 11.0))


scala> val C = A.copy
C: breeze.linalg.DenseMatrix[Double] =
1.0   2.0   3.0   2.0
1.0   3.0   5.0   5.0
2.0   4.0   7.0   1.0
-1.0  -2.0  -6.0  -7.0

scala>  C(3,::) := nl
res1: breeze.linalg.Transpose[breeze.linalg.DenseVector[Double]] = Transpose(DenseVector(1.0, 4.0, 6.0, 11.0))

scala> C
res2: breeze.linalg.DenseMatrix[Double] =
1.0  2.0  3.0  2.0
1.0  3.0  5.0  5.0
2.0  4.0  7.0  1.0
1.0  4.0  6.0  11.0

scala> det(C)
ago 19, 2016 6:48:17 PM com.github.fommil.netlib.LAPACK <clinit>
WARNING: Failed to load implementation from: com.github.fommil.netlib.NativeSystemLAPACK
ago 19, 2016 6:48:17 PM com.github.fommil.netlib.LAPACK <clinit>
WARNING: Failed to load implementation from: com.github.fommil.netlib.NativeRefLAPACK
res3: Double = -0.0

So we have now a matrix that we can use for that. We must decompose it in singular values and look for the zero values

scala> val svd.SVD(u,s,v) = svd(C)
u: breeze.linalg.DenseMatrix[Double] =
-0.2418695880246191   0.18180320883181855  0.8749797442170381    -0.3779644730092261
-0.4572321583765708   0.05780050748664106  -0.46494008565837486  -0.755928946018455
-0.39944397391966924  0.8267072956674623   -0.11892189088772076  0.3779644730092271
-0.7568899308580912   -0.5293030718623615  0.0640214637880056    0.3779644730092274
s: breeze.linalg.DenseVector[Double] = DenseVector(16.921266409229123, 5.964439026615583, 0.31017770016412793, 6.020650824737852E-16)
v: breeze.linalg.DenseMatrix[Double] =
-0.13325714344103542  -0.3829956407255237  -0.6116100715073144  -0.6793305479205232
0.22864098865050173   0.28948654309971367  0.5776812852057681   -0.7281518882733954
0.7615548778852732    0.43696733513844804  -0.4774219714970357  0.03408...
scala> s
res4: breeze.linalg.DenseVector[Double] = DenseVector(16.921266409229123, 5.964439026615583, 0.31017770016412793, 6.020650824737852E-16)

We can see that the last value is null (6.020650824737852E-16 ~ 0) There could be several zero values, but if the matrix has determinant 0, there will be always at least one. We now create a vector full of zeros except in the position of our null singular values and multiply the transpose of the matrix v by it

scala> val nts =  v.t * DenseVector(0,0,0,1.0)
nts: breeze.linalg.DenseVector[Double] = DenseVector(0.5916079783099643, -0.7606388292556632, 0.25354627641855365, 0.08451542547285162)

this is the non trivial solution you wanted. We can check it:

scala> C * nts
res5: breeze.linalg.DenseVector[Double] = DenseVector(2.1094237467877974E-15, 1.4432899320127035E-15, 2.9976021664879227E-15, 1.4432899320127035E-15)

And we can see it is 0 except for rounding errors.