Solving a linear system with circulant matrix using FFT

solve-circulant.txt

import numpy as np
from scipy.linalg import circulant

def solve_circulant(A,b):
    return np.fft.ifft(np.fft.fft(b)/np.fft.fft(A[:,0]))

n = 10000
a = np.random.randn(1,n)
A = circulant(a)
b = np.random.rand(n)

import time
t = time.time()
result_numpy = np.linalg.solve(A, b)
print('np.linalg.solve:', time.time()-t, 'seconds')
print('Residual:', np.linalg.norm(A@result_numpy-b))

print('--------------------')

t = time.time()
result_solve_circulant = solve_circulant(A, b)
print('solve_circulant2:', time.time()-t, 'seconds')
print('Residual:', np.linalg.norm(A@result_solve_circulant-b))