On a Toeplitz Representation of the H1/2 Norm

Some representations of the H1/2 norm are used as Schur complement preconditioner in PCG based domain decomposition algorithms for elliptic problems. These norm representations are efficient preconditioners but the corresponding matrices are dense, so they need FFT algorithm for matrix-vector multiplications. Here we give a new matrix representation of this norm by a special Toeplitz matrix. It contains only O(log(n)) different entries at each row, where n is the number of rows and so a matrix-vector computation can be done by O(nlog(n)) arithmetic operation without using FFT algorithm. The special properties of this matrix assure that it can be used as preconditioner. This is proved by estimating spectral equivalence constants and this fact has also been verified by numerical tests.