You are an expert at summarizing long articles. Proceed to summarize the following text: 
with the development of electromagnetic and optics technology and the increasing demands in industrial and military applications , scattering from periodic structures @xcite have attracted much interest in recent years . a variety of numerical methods including finite difference methods @xcite , finite element methods @xcite , spectral and spectral element methods @xcite , integral equation methods @xcite , dirichlet - to - neumann map methods @xcite , and mode expansion method @xcite have been developed by the engineering community and the applied mathematical community for solving linear diffraction problems from periodic structures . finite difference and finite element methods are easy to implement and result in sparse linear systems , which enable the use of sparse direct solvers . however , these methods typically have significant dispersion errors for high - frequency problems and thus fail to provide accurate solutions . if the medium is piecewise constant , boundary integral equations formulated on the interfaces of multilayer structures @xcite or the boundaries of the obstacles @xcite are natural and mathematically rigorous . by exploiting high - order quadratures , one obtains much higher efficiency and accuracy than finite difference and finite element methods . for problems with general medium , spectral methods @xcite can be employed . they are simple to implement and typically require relatively small number of unknowns to attain a fixed accuracy . we refer to @xcite for a brief survey of existing spectral methods for partial differential equations .    in this paper , we consider 2d quasi - periodic scattering problems . by introducing transparent boundary conditions , the problem is governed by a helmholtz equation with variable coefficients defined on rectangular domains . we propose a spectral collocation method and a tensor product spectral method . the first one uses the spectral collocation techniques @xcite and the second one , based on separable representations of the differential operator , combines the fourier spectral method and the ultraspherical spectral method @xcite . for vertically layered medium case , both methods only require to solve a one dimensional problem . the two spectral methods proposed in this paper can adaptively determine the number of unknowns and approximate the solution to a high accuracy . we remark that the tensor product spectral method leads to matrices that are banded or almost banded . by employing the fast algorithm in @xcite , a layered medium approximation problem can be used as a preconditioner for the problem with general media . recently , chebfun software @xcite was extended to solve problems in two dimensions @xcite , both of which are nonperiodic . we refer to @xcite for the summary of the mathematics and algorithms of chebyshev technology for nonperiodic functions . extension to periodic functions in one dimension was proposed in @xcite . our spectral methods can be used to solve the problems in two space dimensions , one of which is periodic . implementing our methods with the adaptive strategies of chebfun software is easy . the rest of this paper is organized as follows . in 2 the model problem is formulated and further reduced to a boundary value problem . in 3 we present the spectral collocation method for the problem . section 4 is devoted to the tensor product spectral method . numerical examples illustrating the accuracy and efficiency of the methods are reported in  5 . we present brief concluding remarks in  6 . assume that no currents are present and that the fields are source free . then the electromagnetic fields in the whole space are governed by the following time - harmonic maxwell equations ( time dependence @xmath0 ) & & = h , [ me1 ] + & & = -,[me2]where @xmath1 is the imaginary unit , @xmath2 is the angular frequency , @xmath3 is the permeability , @xmath4 is the permittivity , @xmath5 is the electric field and @xmath6 is the magnetic field .    in this paper , we consider a simple quasi - periodic scattering model : @xmath3 is constant everywhere ; @xmath4 is periodic in @xmath7 variable of period @xmath8 , invariant in @xmath9 variable , and constant away from the region @xmath10 , i.e. , there exist constants @xmath11 and @xmath12 such that & & ( x , y , z)=^+ , y > 1- , + & & ( x , y , z)=^- , y < -1 . in the tm polarization , the electric field @xmath5 takes the simpler form @xmath13 the maxwell equations ( [ me1])-([me2 ] ) yield the helmholtz equation : u+ ^2u=0.[reduv1 ]    consider the plane wave @xmath14 is incident from the above , where @xmath15 , @xmath16 , and @xmath17 is the angle of incidence with respect to the positive @xmath18-axis . the incident wave @xmath19 leads to reflected wave @xmath20 and transmitted wave @xmath21 . for @xmath22 , we have @xmath23 , and for @xmath24 , @xmath25 . we are interested in quasi - periodic solution @xmath26 with phase @xmath27 , i.e. , @xmath28 is @xmath8-periodic in @xmath7 variable . therefore , the reflected and transmitted waves can be written as & & u^r=_j r_j^_jx+_jy , y>1 , + & & u^t=_j t_j^_jx-_jy , y<-1 , where @xmath29 and @xmath30 are unknown complex scalar coefficients and & & _ j=_0+j , + & & _ j=,(_j)0 , + & & _ j= , ( _ j)0.note that if @xmath31 is real , then the @xmath32 s satisfying @xmath33 correspond propagating modes . throughout , we assume that @xmath34 and @xmath35 for all @xmath36 . this assumption excludes the `` resonant '' cases , where waves can propagate along the @xmath7-axis .    for a quasi - periodic function @xmath37 , define the linear operators @xmath38 and @xmath39 by @xcite & & ( sf)(x)=_j_j f_j^_j x,[mcals ] + & & ( t f ) ( x)=_j_j f_j ^_j x,[mcalt]where & & f ( x)=_jf_j ^_j x , + & & f_j = _ 0 ^ 2f ( x)^-_j xx.let @xmath40 denote the unit outward normal . we obtain transparent boundary conditions : [ dtn ] & & _ u - su=-2_0^_0 x-_0,(0,2)\{1 } , + & & _ u - t u=0,(0,2)\{-1}.[dtnn ] the quasi - periodic scattering problem is to solve the helmholtz equation ( [ reduv1 ] ) in the rectangular domain @xmath41 subject to the transparent boundary conditions ( [ dtn])-([dtnn ] ) and the quasi - periodic boundary condition & & u(x+2,y)=^_0 2u(x , y).[qp ]    define @xmath42 . then @xmath43 satisfies [ periodic]\ {    lll__0 v+^2v=0 , & in & =(0,2)(-1,1 ) , + _ y v-^-_0 xs ( ^_0 xv)=-2_0 ^ -_0 , & on & ( 0,2 ) , + _ xt(^_0 xv)=0 , & on & ( 0,2 ) , + v(x+2,y)=v(x , y ) , & in & ^2 ,    .where the operator @xmath44 is defined by @xmath45 . the solution to ( [ periodic ] ) is unique at all but a discrete set of frequencies @xmath2 when the incident angle @xmath46 is fixed . existence and uniqueness of the solution is strictly proved in dobson @xcite by a variational approach .    since the operators @xmath38 and @xmath39 given in ( [ mcals])-([mcalt ] ) are defined by infinite series , the computation has to be truncated in practice . for simplicity , we truncate @xmath38 and @xmath39 as follows : & & ( s^n f)(x)=_j=1-q^n - q_jf_j^_j x , + & & ( t^n f ) ( x)=_j=1-q^n - q_j f_jt^n ^_j x , where @xmath47 is a sufficiently large integer and @xmath48 is an integer satisfying that @xmath49 and all propagating modes are contained in the middle of the truncated series . next , we propose two spectral methods for the following problem [ tperiodic]\ {    lll__0 v+^2v=0 , & in & =(0,2)(-1,1 ) , + _ y v-^-_0 xs^n(^_0 xv)=-2_0 ^ -_0 , & on & ( 0,2 ) , + _ y v+^-_0 xt^n(^_0 xv)=0 , & on & ( 0,2 ) , + v(x+2,y)=v(x , y ) , & in & ^2 . .we refer to ( * ? ? ? * section 3.1 ) for the discussion on the existence and uniqueness of the solution of the problem ( [ tperiodic ] ) . in this paper , we focus on the accurate and efficient spectral methods for the problem ( [ tperiodic ] ) . thus we always assume that the discrete problem has a unique solution . we approximates the problem ( [ tperiodic ] ) by fourier discretization in @xmath7 variable and chebyshev discretization in @xmath18 variable . let @xmath50 and @xmath51 with @xmath52 , @xmath53 , and @xmath54 . introduce the first - order fourier differentiation matrix @xcite , @xmath55_{i , j=1}^{n}$ ] , n , & & d_ij^x = \ {    ll 0 , & i = j , + ( -1)^i - j , & ij ,    . + n , & & d_ij^x = \ {    ll 0 , & i = j , + ( -1)^i - j , & ij ,    .the second - order fourier differentiation matrix @xcite , @xmath56_{i , j=1}^{n}$ ] , n , & & d_ij^xx = \ {    ll -+ , & i = j , + ( -1)^i - j+1 , & ij ,    . + n , & & d_ij^xx = \ {    ll -- , & i = j , + ( -1)^i - j+1 ^ 2 , & ij ,    .and the @xmath57 chebyshev differentiation matrix @xcite , @xmath58_{i , j=0}^m,$ ] & & d_00^y=,d_mm^y=- , + & & d_ii^y=-,i=1,  ,m-1 , + & & d_ij^y= , ij , i , j=0,1,  ,m , + & & c_i = \ {    ll 2 , & i=0 m , + 1 , &    .the discretization of the helmholtz equation in ( [ tperiodic ] ) takes the form [ discrete ] * p**v**d*_xx^+2_0*p**v**d*_x^-|_0|^2*p**v*+*p**d*_y^2*v*+^2()=*0*,where @xmath59 is the @xmath60 matrix obtained by deleting the first and last rows of the identity matrix @xmath61 , @xmath62_{m=0,n=1}^{m , n}$ ] , @xmath63 is the approximate solution at the point @xmath64 , @xmath65_{m=0,n=1}^{m , n}$ ] , @xmath66 , and @xmath67 denotes the componentwise product . the operators @xmath68 and @xmath69 can be approximated by @xmath70 matrices : [ s ] & & * s*=*g*^*_:=*g*^*\{_1-q,_2-q,,_n - q}*g * , + [ t ] & & * t*=*g*^*_:=*g*^*\{_1-q,_2-q,,_n - q}*g*,where @xmath71 is the @xmath70 matrix with @xmath72 entry @xmath73 , @xmath74 . the discrete forms of the transparent boundary conditions are given by [ beta1 ] & & * e*_0^_y*v*-*e*_0^^=-2_0 ^ -_0 * e*^ , + [ gamma1 ] & & * e*_m^_y*v*+*e*_m^^= * 0*,where & & * e*_0=[1  0  0]^^m+1 , + & & * e*_m=[0  0  1]^^m+1 , + & & * e*=[1  1  1]^^n . let [ helm]*h*= ( * d*_xx+2_0*d*_x-|_0|^2 * i*_n)+*i*_n(*pd*_y^2)+^2(*i*_n ) \{()}.combining ( [ discrete ] ) , ( [ beta1 ] ) and ( [ gamma1 ] ) yields the linear system [ global ] * a**v*=*g*,where =  [    c*i*_n(*e*_0^_y)-*s*_0^ + * h * + * i*_n(*e*_m^_y)+*t*_m^    ] , and @xmath75\in\mbbc^{mn+n}.\ ] ]    the matrix @xmath76 in ( [ discrete ] ) is called the downsampling matrix @xcite obtained by using the inner chebyshev points of the second kind,@xmath77 as resampling points . one might choose other points , such as the chebyshev points of the first kind , @xmath78 we refer to @xcite for explicit construction of rectangular differentiation matrix @xmath79 . assume that the medium in @xmath80 is vertically layered , i.e. , @xmath81 . then , the matrix @xmath82 in ( [ helm ] ) takes the form @xmath83 where @xmath84 let @xmath85 be the discrete fourier transform matrix with @xmath72 entry @xmath86 , @xmath87 we have the following propositions . the proofs are straightforward . [ pfft ] the matrices @xmath88 in ( [ s ] ) and @xmath89 in ( [ t ] ) satisfy @xmath90 where _ s&=&\{_1^,_2^,,_n^ } + & = & \{_0,_1,,_n - q,_1-q,_2-q,,_-1},and _ t&=&\{_1^,_2^,,_n^ } + & = & \{_0,_1,,_n - q,_1-q,_2-q,,_-1}.    [ diag ] the first - order spectral differentiation matrix @xmath91 and the second - order spectral differentiation matrix @xmath92 can be diagonalized by @xmath85 . specifically , we have @xmath93 where _ x&=&\{_1^x,_2^x,,_n^x } + & = & \ {    ll\{0,1,,(n-1)/2,(1-n)/2,(3-n)/2,,-1 } , & , + \{0,1,,n/2 - 1,0,1-n/2,2-n/2,,-1 } , & ,    .and _ xx&=&\{_1^xx,_2^xx,,_n^xx } + & = & \ {    ll-\{0,1,4,,((n-1)/2)^2,((1-n)/2)^2,,4,1 } , & , + -\{0,1,4,,(n/2)^2,(n/2 - 1)^2,,4,1 } , & .    .    multiplying the linear system ( [ global ] ) by @xmath94\ ] ] from the left yields [ uncoupled] [    c*i*_n(*e*_0^_y)-_s_0^ + ( _ xx+2_0_x-|_0|^2 * i*_n)+*i*_n(*p*(*d*_y^2+^2^y ) ) + * i*_n(*e*_m^_y)+_t_m^    ] = , where @xmath95,\qquad \wh{\bf e}={\bf fe}=\l[\begin{array}{c}\sqrt{n}\\ { \bf 0}\end{array}\r].\ ] ] reordering the unknowns and equations in ( [ uncoupled ] ) , we obtain @xmath47 uncoupled linear systems of order @xmath96 : [ oned] [    c*e*_0^_y-_0*e*_0^ + * p*(*d*_y^2+^2^y)-|_0|^2*p * + * e*_m^_y+_0*e*_m^    ] _ 1= [    c -2_0 ^ -_0 + * 0 * + 0    ] , and for @xmath97 , @xmath98\wh{\bf v}_i={\bf 0},\ ] ] where @xmath99 is the @xmath100-th column of @xmath101 . obviously , @xmath102 for @xmath103 . after solving the linear system ( [ oned ] ) , we obtain @xmath104 by @xmath105 . we propose a tensor product spectral method ( see  4.3 ) for the problem ( [ tperiodic ] ) by combining the fourier spectral method and the ultraspherical spectral method @xcite . we consider the second - order linear ordinary differential equation ( ode ) [ pode ] w:=a(x)w(x)+b(x)w(x)+c(x)w(x)=f(x),xwith periodic boundary conditions . here , @xmath106 , @xmath107 , @xmath108 and @xmath37 are periodic functions on @xmath109 $ ] . the fourier spectral method finds an infinite vector @xmath110^\rmt,\ ] ] such that the fourier expansion of the solution of ( [ pode ] ) is given by @xmath111.\ ] ]    note that we have @xmath112 the first - order differentiation operator is given by @xmath113,\ ] ] and the second - order differentiation operator is given by @xmath114 in order to handle variable coefficients of the forms @xmath115 , @xmath116 and @xmath117 in ( [ pode ] ) , we need to represent the multiplication of two fourier series as an operator on coefficients . let @xmath118 $ ] denote the multiplication operator that represents multiplication of two fourier series , i.e. , if @xmath119 is a vector of fourier expansion coefficients of @xmath120 , then @xmath118{\bf w}$ ] returns the fourier expansion coefficients of @xmath121 . suppose that @xmath106 is given by its fourier series @xmath122 then the explicit formula for @xmath118 $ ] is given by the following toeplitz operator @xmath123=\l[\begin{array}{ccc } \ddots & \vdots & \ddots\\ \ddots & a_{-2 } & \ddots\\ \ddots & a_{-1 } & \ddots\\ \ddots & a_0 & \ddots \\ \ddots & a_1 & \ddots \\ \ddots & a_2 & \ddots \\ \ddots & \vdots & \ddots \end{array}\r].\ ] ] this multiplication operator looks dense ; however , if @xmath106 is approximated by a _ trigonometric polynomial of degree @xmath124 _ , then @xmath118 $ ] is banded with a bandwidth of @xmath124 . combining the differentiation and multiplication operators yields @xmath125\mcald_x^2+\mcalt[b]\mcald_x+\mcalt[c]){\bf w}={\bf f},\ ] ] where @xmath126 and @xmath127 are vectors of fourier expansion coefficients of @xmath120 and @xmath37 , respectively . we need truncate the operator to derive a practical numerical scheme . let @xmath128 be the projection operator satisfying @xmath129{\bf w}=\l[\begin{array}{cccc } w_{1-q } & w_{2-q } & \cdots & w_{n - q } \end{array}\r]^\rmt.\ ] ] we obtain the following linear system @xmath130 where @xmath131\mcald_x^2+\mcalt[b]\mcald_x+\mcalt[c].\ ] ] the truncation parameter @xmath47 can be adaptively chosen so that the numerical solution approximates the exact solution to relative machine precision . consider the second order linear ordinary differential equation [ code]w:=a(x)w(x)+b(x)w(x)+c(x)w(x)=f(x),where @xmath106 , @xmath107 , @xmath108 , @xmath120 and @xmath37 are functions defined on @xmath132 $ ] . the ultraspherical spectral method finds an infinite vector @xmath133^\rmt\ ] ] such that the chebyshev expansion of the solution of ( [ code ] ) is given by @xmath134,\ ] ] where @xmath135 is the degree @xmath32 chebyshev polynomial . note that we have the following recurrence relation @xmath136 where @xmath137 is the ultraspherical polynomial with an integer parameter @xmath138 of degree @xmath32 @xcite . then the differentiation operator for the @xmath139th derivative is given by [ l0]_=2 ^ -1(-1)! [    ccccc * 0 * & & & & + & & + 1 & & + & & & + 2 & + & & & &    ] , 1.here @xmath140 in ( [ l0 ] ) denotes a @xmath139-dimensional zero row vector . the conversion operator converting a vector of chebyshev expansion coefficients to a vector of @xmath141 expansion coefficients , denoted by @xmath142 , and the conversion operator converting a vector of @xmath143 expansion coefficients to a vector of @xmath144 expansion coefficients , denoted by @xmath145 , are given by @xmath146,\quad \mcals_\lambda=\l[\begin{array}{ccccc}1 & 0 & -\frac{\lambda}{\lambda+2 } & & \\ & \frac{\lambda}{\lambda+1}&0&-\frac{\lambda}{\lambda+3}&\\ & & \frac{\lambda}{\lambda+2}&0 & \ddots\\ & & & \frac{\lambda}{\lambda+3}&\ddots\\ & & & & \ddots \end{array}\r],\ \lambda\geq 1.\ ] ] we also require the multiplication operator @xmath147 $ ] that represents multiplication of two chebyshev series , and the multiplication operator @xmath148 $ ] that represents multiplication of two @xmath143 series , i.e. , if @xmath126 is a vector of chebyshev expansion coefficients of @xmath120 , then @xmath147{\bf w}$ ] returns the chebyshev expansion coefficients of @xmath121 , and @xmath148\mcals_{\lambda-1}\cdots\mcals_0{\bf w}$ ] returns the @xmath143 expansion coefficients of @xmath121 . suppose that @xmath106 has the chebyshev expansion @xmath149 then @xmath147 $ ] can be written as @xcite : @xmath150=\frac{1}{2}\l[\begin{array}{ccccc}2a_0 & a_1 & a_2 & a_3 & \cdots\\ a_1 & 2a_0 & a_1 & a_2 & \ddots \\ a_2 & a_1 & 2a_0 & a_1 & \ddots \\ a_3 & a_2 & a_1 & 2a_0 & \ddots \\ \vdots & \ddots & \ddots & \ddots & \ddots \end{array}\r]+\frac{1}{2}\l[\begin{array}{ccccc } 0 & 0 & 0 & 0 & \cdots\\ a_1 & a_2 & a_3 & a_4 & \cdots \\ a_2 & a_3 & a_4 & a_5 & \iddots \\ a_3 & a_4 & a_5 & a_6 & \iddots \\ \vdots & \iddots & \iddots & \iddots & \iddots \end{array}\r].\ ] ] the explicit formula for the entries of @xmath148 $ ] with @xmath138 is given in @xcite . this multiplication operators @xmath148 $ ] with @xmath151 look dense ; however , if @xmath106 is approximated by a truncation of its chebyshev or @xmath143 series , then @xmath148 $ ] is banded . combining the differentiation , conversion and multiplication operators yields [ dcode](_2[a]_2+_1_1[b]_1+_1_0_0[c])*w*=_1_0*f*,where @xmath126 and @xmath127 are vectors of chebyshev expansion coefficients of @xmath120 and @xmath37 , respectively . we need truncate the operator to derive a practical numerical scheme . let @xmath152 be the projection operator given by @xmath153.\ ] ] we obtain the following linear system @xmath154 where @xmath155\mcald_2+\mcals_1\mcalm_1[b]\mcald_1+\mcals_1\mcals_0\mcalm_0[c].\ ] ]      we seek the approximate solution @xmath157 to the problem ( [ tperiodic ] ) , @xmath158 the linear differential operator in ( [ tperiodic ] ) can be expressed as @xmath159 where @xmath160 , @xmath161 , @xmath162 is the identity operator , and @xmath163 and @xmath164 are the corresponding multiplication operations . the discretization of the helmholtz equation in ( [ tperiodic ] ) takes the form [ tpfc ] * q**c**v**x*^+*q**y**v*+^2^=*0*,where * q * is the @xmath165 matrix obtained by deleting the last two rows of the identity matrix @xmath166 , @xmath167 , @xmath168 , @xmath169 , @xmath170\mcalp_n^\rmt$ ] , @xmath171\mcalq_m^\rmt$ ] , @xmath172_{i=0,j=1-q}^{m-1,n - q}$ ] . the discrete forms of the transparent boundary conditions are given by [ beta2 ] & & * b*_1 ^ -*a*_1^_=-2_0 ^ -_0 * e*_q^ , + [ gamma2 ] & & * b*_2^+*a*_2^_= * 0*,where & & _ = \{_1-q,_2-q,,_n - q } , + & & _ = \{_1-q,_2-q,,_n - q } , + & & * b*_1=[0  1  4  ( m-1)^2]^ , + & & * b*_2=[0  1  -4  ( -1)^m(m-1)^2]^ , + & & * a*_1=[1  1  1]^^m , + & & * a*_2=[1  -1  ( -1)^(m-1)]^^m , and @xmath173 is the @xmath48-th column of the identity matrix @xmath174 . let [ helmfc]*h*= * x*(*qc*)+*i*_n(*qy*)+^2(*q * ) . combining ( [ tpfc ] ) , ( [ beta2 ] ) and ( [ gamma2 ] ) yields the linear system [ globalfc ] * a**v*=*g*,where =  [    c*i*_n_1 ^ -__1^ + * i*_n_2^+__2^ + * h *    ] , and @xmath175\in\mbbc^{mn}.\ ] ]    for general bivariate function @xmath176 , we can use its low rank approximant , i.e. , sum of functions of the form @xmath177 , where @xmath178 and @xmath179 are univariate functions . an algorithm @xcite which is mathematically equivalent to gaussian elimination with complete pivoting can be used to construct low rank approximations .      in this case , we have @xmath180 , i.e. , @xmath181 . then @xmath182 the matrix @xmath82 in ( [ helmfc ] ) takes the form @xmath183 reordering the unknowns and equations in ( [ globalfc ] ) , we obtain [ onedfc] [    c*b*_1 ^ -_0*a*_1^ + * b*_2^+_0*a*_2^ + * q*(*y*+^2-|_0|^2*c * )    ] * v*_q =  [    c -2_0 ^ -_0 + 0 + * 0 *    ] , and [ ofc] [    c*b*_1 ^ -_j - q*a*_1^ + * b*_2^+_j - q*a*_2^ + * q*(*y*+^2-((j - q)^2 + 2_0(j - q)+|_0|^2)*c * )    ] * v*_j=*0*,jq , where @xmath184 is the @xmath32-th column of @xmath185 . obviously , @xmath186 for @xmath187 .    note that the fast algorithm in @xcite can be used to solve the linear system ( [ onedfc ] ) , which requires @xmath188 operations . here , @xmath189 is the number of chebyshev points needed to resolve the function @xmath179 . the coefficient matrix resulting from a layered medium approximation problem can be used as a preconditioner for the problem with general medium . the corresponding computational complexity for the preconditioner solve is @xmath190 . we have performed numerical experiments in numerous cases . in this section , we present a few typical results of these experiments to illustrate the accuracy and efficiency of the two spectral methods . all computations are performed with matlab r2012a . the parameters are chosen as @xmath191 , @xmath192 , @xmath193 , @xmath194 . we consider three cases : & & _ 1(x , y)=(y)=1+^+4 , + & & _ 2(x , y)=1+^+4-((x/2 ) ) , + & & _ 3(x , y)=1+^+4-y((x/2 ) ) . the medium characterized by @xmath195 is vertically layered . the bivariate function @xmath196 is of rank @xmath197 . we use the rank @xmath198 approximant obtained by the algorithm proposed in @xcite to approximate @xmath199 . in figure [ nr ] , we plot the three media and the real parts of the corresponding waves obtained by our spectral methods . we observe that the numerical results obtained by the two methods coincide well for all the three media . we also test the performance of the problem with @xmath195 as a preconditioner for the problem with @xmath199 . the fast algorithm in @xcite is used to solve the linear systems ( [ onedfc ] ) and ( [ ofc ] ) . the gmres algorithm @xcite is used as the iterative solver . the initial guess is set to be the zero vector . gmres with the layered medium preconditioner obtained a solution with the relative residual norm less than @xmath200 at the @xmath201th iteration , while gmres without preconditioning almost stagnates ; see figure [ conhis ] for the convergence history . we have proposed a spectral collocation method and a tensor product spectral method for solving the 2d quasi - periodic scattering problem . both of the methods can adaptively determine the number of unknowns and approximate the solution to a high accuracy . the tensor product spectral method is more interesting because it leads to matrices that are banded or almost banded , which enable the use of the fast , stable direct solver @xcite . based on this fast solver , a layered medium preconditioning technique is used to solve the problem with general media . our methods also apply to solve general partial differential equations in two space dimensions , one of which is periodic . extension of our methods to bi - periodic structure diffraction grating problem @xcite is being considered .
we consider the 2d quasi - periodic scattering problem in optics , which has been modelled by a boundary value problem governed by helmholtz equation with transparent boundary conditions . a spectral collocation method and a tensor product spectral method 
 are proposed to numerically solve the problem on rectangles . 
 the discretization parameters can be adaptively chosen so that the numerical solution approximates the exact solution to a high accuracy . 
 our methods also apply to solve general partial differential equations in two space dimensions , one of which is periodic . 
 numerical examples are presented to illustrate the accuracy and efficiency of our methods . 
 helmholtz equation , transparent boundary condition , spectral method , chebfun    65m70 , 65t40 , 65t50 , 78a45