1
$\begingroup$

Given that I have a set of equations about varible $x_0,x_1,\cdots,x_n$, which own the following style:

$ \left( \begin{array}{cccccccc} \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 \\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ \color{red}{x_0} \\ \color{red}{x_1} \\ \color{red}{x_2} \\ \end{array} \right)=\left( \begin{array}{c} (1,1) \\ (2,3) \\ (3,-1) \\ (4,1) \\ (5,0) \\ \end{array} \right) $

Obviously, I cannot solve this linear system by LinearSolve[]. To solve this equation group, I only used the Solve[].

mat=
 {{1/6, 2/3, 1/6, 0, 0, 0, 0, 0}, {0, 1/6, 2/3, 1/6, 0, 0, 0, 0}, 
  {0, 0, 1/6, 2/3, 1/6, 0, 0, 0}, {0, 0, 0, 1/6, 2/3, 1/6, 0, 0}, 
  {0, 0, 0, 0, 1/6, 2/3, 1/6, 0}};
eqns = mat.{x0, x1, x2, x3, x4, x0, x1, x2};

$ \begin{pmatrix} \frac{x_0}{6}+\frac{2 x_1}{3}+\frac{x_2}{6}\\ \frac{x_1}{6}+\frac{2 x_2}{3}+\frac{x_3}{6}\\ \frac{x_2}{6}+\frac{2 x_3}{3}+\frac{x_4}{6}\\ \frac{x_0}{6}+\frac{x_3}{6}+\frac{2 x_4}{3}\\ \frac{2 x_0}{3}+\frac{x_1}{6}+\frac{x_4}{6} \end{pmatrix} $

yValues = {{1, 1}, {2, 3}, {3, -1}, {4, 1}, {5, 0}};
part1 = {x0, x1, x2, x3, x4} /. 
  Solve[Thread[eqns == yValues[[All, 1]]], {x0, x1, x2, x3, x4}]
part2 = {x0, x1, x2, x3, x4} /. 
  Solve[Thread[eqns == yValues[[All, 2]]], {x0, x1, x2, x3, x4}]
res = Transpose[Join[part1, part2]]
 {{75/11, -8/11}, {-9/11, 4/11}, {27/11, 58/11}, {3, -38/11}, {39/11, 28/11}}

Question

However, the index $n$ for variables $\{x_0,x_1,\cdots,x_n\}$ is very large ($n=100$) in my work. My solution that by Solve[] is very cockamamie. So I would like to know how to deal with this case by the built-in LinearSolve[] efficiently?

$\endgroup$
  • 1
    $\begingroup$ You can partition your x-vector as $(x,y,x)$, where $x=(x_0,x_1,x_2)$ and $y=(x_3,x_4)$, and your matrix mat in a similar way (3x3 block matrix). Multiplying out the blocks and collecting $x$ and $y$ together will give you the linear system of reduced size that you can feed to LinearSolve $\endgroup$ – sebhofer Oct 23 '15 at 8:16
  • 1
    $\begingroup$ Do a fold-over: $$\begin{pmatrix}\frac16&\frac23&\frac16&0&0\\ 0&\frac16&\frac23&\frac16&0\\ 0&0&\frac16&\frac23&\frac16\\ \frac16&0&0&\frac16&\frac23\\ \frac23&\frac16&0&0&\frac16\end{pmatrix} \begin{pmatrix}x_0\\x_1\\x_2\\x_3\\x_4\end{pmatrix} =\begin{pmatrix}(1,1)\\(2,3)\\(3,-1)\\(4,1)\\(5,0)\\\end{pmatrix}$$ Is this part of your closed spline interpolation problem? $\endgroup$ – J. M. is away Oct 23 '15 at 8:33
  • $\begingroup$ @J.M. Yes, see here $\endgroup$ – xyz Oct 23 '15 at 8:41
  • 2
    $\begingroup$ Maybe I missed something in your question. But once you have the equations, you can find the corresponding matrix by CoefficientArrays[eqns, {x0, x1, x2, x3, x4}][[2]] and then use LinearSolve. $\endgroup$ – Fred Simons Oct 23 '15 at 8:59
  • $\begingroup$ @FredSimons Yes, your method is right. I have achieved the right result by your method:) $\endgroup$ – xyz Oct 23 '15 at 9:10
5
$\begingroup$

How to fold a "wide" matrix over to enforce "periodic" conditions:

mat = {{1/6, 2/3, 1/6, 0, 0, 0, 0, 0}, {0, 1/6, 2/3, 1/6, 0, 0, 0, 0},
       {0, 0, 1/6, 2/3, 1/6, 0, 0, 0}, {0, 0, 0, 1/6, 2/3, 1/6, 0, 0},
       {0, 0, 0, 0, 1/6, 2/3, 1/6, 0}};

{m, n} = Dimensions[mat];

LinearSolve[Take[mat, m, m] + PadRight[Take[mat, m, m - n], {m, m}],
            {{1, 1}, {2, 3}, {3, -1}, {4, 1}, {5, 0}}]
   {{75/11, -8/11}, {-9/11, 4/11}, {27/11, 58/11}, {3, -38/11}, {39/11, 28/11}}
$\endgroup$
  • $\begingroup$ Is fold-over the "official" name for this operation? $\endgroup$ – sebhofer Oct 23 '15 at 10:15
  • $\begingroup$ I'm not aware of an official name, but I like the picturesque terminology. :) $\endgroup$ – J. M. is away Oct 23 '15 at 10:18
  • $\begingroup$ I agree. It was just that you so confidently calling it "fold-over" in your comment made me feel like I should have known that it was actually a thing :-) $\endgroup$ – sebhofer Oct 23 '15 at 10:29
  • $\begingroup$ J.M. I would like to ask you a question about well-condition. For a square matrix $A$, I can use the formula $cond(A)=||A|||A^{-1}|||$ to calculate the conditional number of matrix $A$. However, I didn't know which value is proper for well-condition. Thanks a lot. $\endgroup$ – xyz Oct 29 '15 at 2:15
  • $\begingroup$ @Shutao, the idea with conditioning is that the nearer the condition is to $1$, the better the conditioning of the problem (as in the case of orthogonal/unitary matrices). Ill-conditioned systems have large condition numbers, and truly singular systems have infinite condition numbers. $\endgroup$ – J. M. is away Oct 29 '15 at 2:28
4
$\begingroup$
l = 5; s = 3;
(* Solution 1 *)
# + SparseArray[#2, {l, l}] & @@ Internal`PartitionRagged[mat\[Transpose], {l, s}];
LinearSolve[%\[Transpose], yValues]

(* Solution 2 *)
Module[{m = #[[;; l]]}, m[[;; s]] += #[[-s ;;]]; m] &[mat\[Transpose]];
LinearSolve[%\[Transpose], yValues]
$\endgroup$
  • $\begingroup$ Cool, Internal`PartitionRagged can be very useful! $\endgroup$ – sebhofer Oct 23 '15 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.