7
$\begingroup$

I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with

$$\mathbf{A}=\mathbf{T}+\mathbf{C}$$

where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-only matrix:

$$\mathbf{C}=\begin{pmatrix} 0& 0 & \cdots & 0 & c\\ 0 & \ddots & & & 0\\ \vdots & & \ddots & & \vdots\\ 0 & & & \ddots & 0\\ c & 0 & \cdots & 0& 0 \end{pmatrix}$$

What are some efficient algorithms for solving this system of linear equations (i.e. solving for $\mathbf{x}$)?

Improve this question
$\endgroup$
3
  • $\begingroup$ For $C$ clearly we don't need to store the zeros so just store $c_{1,n}$ and $c_{n,1}$ and for $T$ you need just store the bandwidth elements since it is tridiagonal the bandwidth will be $3$. When you do the computation $A= T + C$ computationally it's only $O(n)$. For the storage of $T$ take advantage of the fact that $T$ is symmetric. If none of this makes sense let me know. $\endgroup$
    – Wolfy
    Aug 31, 2016 at 20:21
  • $\begingroup$ @Wolfy You've only told me about how I could/should store the matrix $\mathbf{A}$. You've made no mention of how one might go about solving the linear system, or solving for $\mathbf{x}$ given the matrix $\mathbf{A}$ and the vector $\mathbf{b}$. I obviously would not like to calculate $\mathbf{A}^{-1}$ through an elementary method. $\endgroup$
    – Arturo don Juan
    Aug 31, 2016 at 20:39
  • $\begingroup$ Right sorry hard to see sometimes on a mobile phone. Do you know anything about $LU$ factorization? You can solve $A = LU$ then to solve for $x$ you use a backward and forward solve. Wikipedia explains it in a simple way. $\endgroup$
    – Wolfy
    Aug 31, 2016 at 20:42

1 Answer 1

Reset to default
5
$\begingroup$

A variant of Thomas's algorithm for tridiagonal systems of equations handles this problem. See the Wikipedia page at: https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm

See also the discussion at:

http://www.cfd-online.com/Wiki/Tridiagonal_matrix_algorithm_-TDMA(Thomas_algorithm)

Improve this answer
$\endgroup$
3
  • $\begingroup$ The problem with this approach is that the matrix $\mathbf{C}$ is both singular (when the dimension is greater than 2) and cannot be written as an outer product of vectors. Unless I'm looking at this from the wrong angle, this method doesn't seem to helpful. :( $\endgroup$
    – Arturo don Juan
    Aug 31, 2016 at 23:12
  • $\begingroup$ I've added a second link to the answer that gives an explicit formula for how to use Sherman-Morrison-Woodbury to reduce your problem to the solution of a tridiagonal system (the tridiagonal part of the original matrix is changed.) This is a well known technique. $\endgroup$
    – Brian Borchers
    Aug 31, 2016 at 23:26
  • $\begingroup$ The second link you provided gave me the exact information I needed. My problem becomes effectively reduced to solving two linear systems, each of which concerns a symmetric tridiagonal matrix. On each of these linear systems I can apply the Thomas algorithm and arrive at my solution. $\endgroup$
    – Arturo don Juan
    Sep 1, 2016 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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