Martin Tang - 1 year ago 147
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.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.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)
``````

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download