<jupyter_start><jupyter_text>Tridiagonal System A tridiagonal system for n unknowns may be written as$$a_ix_{i-1} + b_ix_i+ c_ix_{i+1}=d_i $$ where $$ a_1=0,c_n=0$$In matrix form,$$\begin{bmatrix} b_1 & c_1 &  & &&0 \\ a_2 & b_2 &c_2& & &\\ 0 & a_3 &b_3&c_3&&\\ &  &... &&&\\&  &&&a_n&b_n\\ \end{bmatrix} *\begin{bmatrix} x_1\\x_2\\  \\..\\x_n \end{bmatrix} =\begin{bmatrix} d_1\\d_2\\  \\..\\d_n \end{bmatrix} $$ This tridiagonal matrix has financial applications,e.g solving finite difference method on Black-Scholes PDE. Solving this matrix requries $O(n)$ instead of $O(n^3) $with traditional  Gaussian elimination<jupyter_code>import numpy as np
def tridiag(a, b, c, k1=-1, k2=0, k3=1):
    """Create Tridiagonal matrix,
    Take list a,b,c as diagonals and return the tridiagonal matrix"""
    if len(a)+1!=len(b) or len(a)!=len(c) or len(b)-1!=len(c): ## check if a,b,c size matching, len(a)=len(b)-1=len(c)
        raise ValueError('size of diagonal not matching')
    return np.diag(a, k1) + np.diag(b, k2) + np.diag(c, k3)
a = np.array([1, 1,1,1,1,1,1]); b = np.array([2, 2, 2,2,2,2,2,2]); c =np.array( [3, 3,3,3,3,3,3])
A = tridiag(a, b, c)
A
def TDMAsolver(a, b, c, d):
    '''
    Thomas algorithm for solving tridiagonal linear systems
    https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm
    take a,b,c as tridiagonal matrix, d as dependent values, find the tridigonal matrix solution X such that AX=d
    better than gaussian, O(n)
    '''
    if len(a)+1!=len(b) or len(a)!=len(c) or len(b)-1!=len(c): ## check if a,b,c size matching, len(a)=len(b)-1=len(c)
        raise ValueError('size of diagonal not matching')
    n = len(d) # number of equations
    solution=[0]*n
    for i in range(0, n-1):
        w=a[i]/b[i]
        b[i+1]=b[i+1]-w*c[i]
        d[i+1]=d[i+1]-w*d[i]
        
    solution[n-1]=d[n-1]/b[n-1]
    for j in range(n-2,-1,-1):
        solution[j]=(d[j]-(c[j]*solution[j+1]))/b[j]

    return solution
a = np.array([3.,1,3]) 
b = np.array([10.,10.,7.,4.])
c = np.array([2.,4.,5.])
d = np.array([3,4,5,6.])
A =tridiag(a,b,c) 
## compare with build-in linear solver
import timeit
start = timeit.default_timer()
print('numpy solution = ',np.linalg.solve(A, d))
stop = timeit.default_timer()
print('numpy linear solver time cost : ', stop - start,"sec")

start = timeit.default_timer()
print('TDMA solver solution = ',TDMAsolver(a,b,c,d))
stop = timeit.default_timer()
print('Mine tridiagonal solver time cost: ', stop - start,"sec")<jupyter_output>numpy solution =  [ 0.14877589  0.75612053 -1.00188324  2.25141243]
numpy linear solver time cost :  0.026336799999967297 sec
TDMA solver solution =  [0.1487758945386064, 0.756120527306968, -1.001883239171375, 2.2514124293785316]
Mine tridiagonal solver time cost:  0.0004096000000117783 sec
{'fraction_non_alphanumeric': 0.18635547576301617, 'fraction_numerical': 0.08186714542190306, 'mean_word_length': 3.9049295774647885, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '410303', 'license': 'MIT', 'n_tokens_mistral': 1260, 'n_tokens_neox': 1156, 'n_words': 274, 'path': 'TridiagonalSolver.ipynb', 'repo_name': 'jingshenghua/QuantTopics', 'size': '2785'}