Patent Publication Number: US-10330712-B2

Title: Order O(1) algorithm for first-principles calculation of transient current through open quantum systems

Description:
CROSS-REFERENCE TO RELATED PATENT APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 62/290,717 filed Feb. 3, 2016, which is incorporated herein by reference in its entirety. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to a transient current calculation as part of the study of the response time and peak transient current in the design of nano-chips in nano electronics. 
     BACKGROUND OF THE INVENTION 
     At the heart of growing demands for nanotechnology is the need of ultrafast transistors whose response time is one of the key performance indicators. The response of a general quantum open system can be probed by sending a step-like pulse across the system and monitoring its transient current over time, thus making transient dynamics a very important consideration. Many experimental data show that most molecular device characteristics are closely related to the material and chemical details of the device structure. Therefore, first principles analysis, which involves quantitative and predictive analysis of device characteristics, especially their dynamic properties, without relying on any phenomenological parameter, becomes a central interest in the design of nanoelectronics. 
     The theoretical study of transient current dates back twenty years to when the exact solution in the wideband limit (“WBL”) was obtained by Wingreen et al. See, N. S. Wingreen et al.,  Phys. Rev. B  48, 8487(R) (1993), which is incorporated herein by reference in its entirety. Since then transient current has been studied extensively using various methods, including the scattering wave function, non-equilibrium Green&#39;s function (“NEGF”) approach, and density matrix method. See, J. Wang,  J. Comput. Electron.  12, 343-355 (2013); S. Kurth et al.,  Phys. Rev. B  72, 035308 (2005)(hereinafter “Kurth”); G. Stefanucci et al,  Phys. Rev. B  77, 075339 (2008)(hereinafter “Stefanucci”); Y. Zhu et al.,  Phys. Rev. B  71, 075317 (2005); J. Maciejko et al.,  Phys. Rev. B  74, 085324 (2006)(hereinafter “Maciejko”); R. Tuovinen et al.,  Phys. Rev. B  89, 085131 (2014)(herein after “Tuovinen”); R. Seoane Souto et al.,  Phys. Rev. B  92, 125435 (2015) and X. Zheng et al.,  Phys. Rev. B  75, 195127 (2007), all of which are incorporated herein by reference. The major obstacle to the theoretical investigation of transient current is its computational complexity. Many attempts have been made trying to speed up the calculation See Kurth and Tuovinen, as well as L. Zhang et al.,  Phys. Rev. B  86, 155438 (2012); B. Gaury et al.,  Phys. Rep.  534, 1-37 (2014); M. Ridley et al.,  J. Phys.: Conf. Ser.  696, 012017 (2016)(hereinafter “Ridley”); H A. Croy et al.,  Phys. Rev. B  80, 245311 (2009) and F J. Weston et al.,  Phys. Rev. B  93, 134506 (2016), all of which are incorporated herein by reference in their entirety. 
     Despite these efforts, the best algorithm for calculating the transient current from first principles going beyond WBL limit scales like TN 3  using a complex absorbing potential (“CAP”), where T and N are the number of time steps and the size of the system, respectively. See, L. Zhang et al,  Phys. Rev. B  87, 205401 (2013) (hereinafter “Zhang”), which is incorporated herein by reference in its entirety. It should be noted that if WBL is used, the scaling is reduced. See, the Ridley article. However, to capture the feature of the band structure of the lead and the interaction between the lead and the scattering region, WBL is not a good approximation in the first principles calculation. As a result, most of the first principles investigations of transient dynamics were limited to small and simple one-dimensional systems. 
     There are a number of problems, such as with magnetic tunneling junctions (MTJ) and ferroelectric tunneling junctions, where the system is two dimensional or even three dimensional in nature. See, Z. Y. Ning et al.,  Phys. Rev. Lett.  100, 056803 (2008) and J. D. Burton et al.,  Phys. Rev. Lett.  106, 157203 (2011), which are incorporated herein by reference in their entirety. For these systems, a large number of k points N k  have to be sampled in the first Brillouin to capture accurately the band structure of the system. For MTJ structures like Fe—MgO—Fe, at least N k =10 4  k points must be used to give a converged transmission coefficient. See, D. Waldron et al.,  Phys. Rev. Lett.  97, 226802 (2006), which is incorporated herein by reference in its entirety. This makes the time consuming transient calculation N k  times longer, which is an almost impossible task even with high performance supercomputers. Clearly it is urgent to develop better algorithms to reduce the computational complexity. 
     SUMMARY OF THE INVENTION 
     According to the present invention a novel algorithm based on NEGF-CAP formalism is used to calculate transient current as a function of time step T. The computational time of this algorithm is independent of T as long as T&lt;N 2  where N is the system size. Hence the algorithm is order O(1) as long as T&lt;N 2 . Four important factors are essential to achieve this result: (1) the availability of an exact solution of transient current based on a non-equilibrium Green&#39;s function (NEGF) that goes beyond the wideband limit (WBL); (2) the use of complex absorbing potential (CAP) so that the transient current can be expressed in terms of poles of Green&#39;s function; (3) within the NEGF-CAP formalism the transient current can be calculated separately in the space and time domains making the O(1) algorithm possible so that at this point the computational complexity reduces to 50N 3 +TN 2  (algorithm I); and (4) the exploitation of a Vandermonde matrix enables the use of the fast multipole method (FMM) and fast Fourier transform (FFT) to further reduce the scaling to 50N 3 +2N 2  log 2  N for T&lt;N 2  and large N, which is therefore completely independent of T (algorithm II). See V. Rokhlin,  J. Comput. Phys.,  60, 187-207 (1985)(hereinafter “Rokhlin”) and J. Song et al.,  IEEE trans. Antennas Propagat.  45, 1488-1493 (1997)(hereinafter “Song”), which are both incorporated herein by reference in their entirety. It is possible with this new algorithm to calculate, and thus predict, the actual response of a nano-device theoretically without experimental data. Thus, the algorithm is useful in the design of a nano-device before actual production. 
     Everything is made of atoms. In theory, every physical phenomena in a real device can be accurately calculated and predicted once its composition is known, e.g., how many atoms, which types of atoms, etc. From the Hamiltonian (a quantity that stores the physical information of the system based on the particular electrons of particular elements present in the devices), it is possible to use the algorithm of the present invention to calculate and predict the actual response of a nano-device. To verify the computational complexity, benchmark calculations were carried out on graphene nanoribbons using the tight-binding model. A speed up factor of 1000T was gained for a system size of N=2400. A calculation was also done for the same system with N=10,200 and T=10 8  confirming the O(1) scaling. This fast algorithm makes the computational complexity of transient current calculation comparable to that of a static calculation. Thus, the huge speed gain enables the performance of first principles transient calculations and nano-device design on a modest computer workstation. 
     For a general open quantum system with multiple leads under a step-like bias pulse, the Hamiltonian (the operator corresponding to the total energy of the system in most of the cases) is given by 
     
       
         
           
             
               
                 H 
                 ⁡ 
                 
                   ( 
                   t 
                   ) 
                 
               
               = 
               
                 
                   
                     ∑ 
                     
                       k 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       α 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       ϵ 
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         α 
                       
                     
                     ⁢ 
                     
                       
                         c 
                         ^ 
                       
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         α 
                       
                       † 
                     
                     ⁢ 
                     
                       
                         c 
                         ^ 
                       
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         α 
                       
                     
                   
                 
                 + 
                 
                   
                     ∑ 
                     n 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       ( 
                       
                         
                           ϵ 
                           n 
                         
                         + 
                         
                           
                             U 
                             n 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                       ) 
                     
                     ⁢ 
                     
                       
                         d 
                         ^ 
                       
                       n 
                       † 
                     
                     ⁢ 
                     
                       
                         d 
                         ^ 
                       
                       n 
                     
                   
                 
                 + 
                 
                   
                     ∑ 
                     
                       k 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       α 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       n 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       h 
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         α 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         n 
                       
                     
                     ⁢ 
                     
                       
                         c 
                         ^ 
                       
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         α 
                       
                       † 
                     
                     ⁢ 
                     
                       
                         d 
                         ^ 
                       
                       n 
                     
                   
                 
                 + 
                 
                   c 
                   . 
                   c 
                   . 
                 
               
             
             , 
           
         
       
     
     where c †  (c) denotes the electron creation (annihilation) operator in the lead region. The first term in this equation corresponds to the Hamiltonian of leads with ε k     α    the energy of lead α which contains external bias voltage υ α (t)=V α θ(±t). The second and third terms represent the Hamiltonian in the central scattering region and its coupling to leads, respectively. Also included is the time-dependent Coulomb interaction U n (t) in the scattering region. This Hamiltonian can be obtained using the first-principle method or it can be assumed to be a tight-binding form. Taking q=h=l, the time-dependent terminal current I α (t) of lead α is defined as in the Zhang article.
 
 I   α ( t )= ReTr [ Γ   α (2 H ( t )− i∂   t ) G   &lt; ( t,t ) Γ   α ],  (1)
 
     where  Γ   α  is an auxiliary projection matrix which is used for measuring the transient current passing through the lead α. Here G &lt;  and H(t) are the lesser Green&#39;s function and the Hamiltonian of the central scattering region, respectively. For a step-like pulse an exact solution for G &lt;  has been obtained by Maciejko et al. as described in the Maciejko article, which goes beyond the WBL and has been applied to first principles calculation of transient current for atomic junctions. Next, the case of an upward pulse v α (t)=V α Θ(t) can be considered. In order to have an exact solution as described in the Maciejko article, it is assumed that U n (t)=U n,eq +(U n,neq −U n,eq )Θ(t) where U n,eq  is the equilibrium Coulomb potential, while U n,neq  is the non-equilibrium potential at a long time limit. Note that the fast algorithm relies on this approximation where the self-consistent Coulomb potentials are needed only at two points: t=0 −  and t=∞. As a result of this approximation, at t=0, the system is in equilibrium with Hamiltonian H eq  while at t&gt;0 the system is in a non-equilibrium state with a time-independent Hamiltonian H neq . In terms of a spectral function A α (ε,t), the lesser Green&#39;s function G &lt;  is given by the Maciejko article as 
     
       
         
           
             
               
                 
                   
                     
                       G 
                       &lt; 
                     
                     ⁡ 
                     
                       ( 
                       
                         t 
                         , 
                         t 
                       
                       ) 
                     
                   
                   = 
                   
                     i 
                     ⁢ 
                     
                       
                         ∑ 
                         α 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ∫ 
                         
                           
                             · 
                             d 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           ɛ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           π 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             f 
                             ⁡ 
                             
                               ( 
                               ɛ 
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               A 
                               α 
                             
                             ⁡ 
                             
                               ( 
                               
                                 ɛ 
                                 , 
                                 t 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               Γ 
                               α 
                             
                             ⁡ 
                             
                               ( 
                               ɛ 
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               
                                 A 
                                 α 
                                 † 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   ɛ 
                                   , 
                                   t 
                                 
                                 ) 
                               
                             
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     The upward step-like bias pulse the A α (ε,t) is found in the Maciejko article to be 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             A 
                             α 
                           
                           ⁡ 
                           
                             ( 
                             
                               ϵ 
                               , 
                               t 
                             
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             
                               
                                 G 
                                 _ 
                               
                               r 
                             
                             ⁡ 
                             
                               ( 
                               
                                 ϵ 
                                 + 
                                 
                                   Δ 
                                   α 
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             ∫ 
                             
                               
                                 
                                   d 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   ω 
                                 
                                 
                                   2 
                                   ⁢ 
                                   π 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                 
                               
                               ⁢ 
                               
                                 
                                   
                                     e 
                                     
                                       
                                         - 
                                         
                                           i 
                                           ⁡ 
                                           
                                             ( 
                                             
                                               ω 
                                               - 
                                               ϵ 
                                             
                                             ) 
                                           
                                         
                                       
                                       ⁢ 
                                       t 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       
                                         G 
                                         _ 
                                       
                                       r 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       
                                         ω 
                                         + 
                                         
                                           Δ 
                                           α 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 
                                   ( 
                                   
                                     ω 
                                     - 
                                     ϵ 
                                     + 
                                     
                                       Δ 
                                       α 
                                     
                                     - 
                                     
                                       i 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         0 
                                         + 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               × 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           [ 
                           
                             
                               
                                 Δ 
                                 α 
                               
                               
                                 ( 
                                 
                                   ω 
                                   - 
                                   ϵ 
                                   - 
                                   
                                     i 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       0 
                                       + 
                                     
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               Δ 
                               ⁢ 
                               
                                 
                                   
                                     G 
                                     ~ 
                                   
                                   r 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   ϵ 
                                   ) 
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         
                           ≡ 
                             
                           ⁢ 
                           
                             
                               
                                 A 
                                 
                                   1 
                                   ⁢ 
                                   α 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   ϵ 
                                   + 
                                   
                                     Δ 
                                     a 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               ∫ 
                               
                                 d 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 ω 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   e 
                                   
                                     
                                       - 
                                       
                                         i 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             ω 
                                             - 
                                             ϵ 
                                           
                                           ) 
                                         
                                       
                                     
                                     ⁢ 
                                     t 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     A 
                                     
                                       2 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       α 
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       ω 
                                       , 
                                       ϵ 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     where  G   r  and {tilde over (G)} r  are the non-equilibrium and equilibrium retarded Green functions, respectively, Δ α  is the amplitude of the external bias −V α , and Δ=U neq −U eq  is a matrix where the subscript “neq” and “eq” refer to non-equilibrium and equilibrium potentials, respectively. 
     Despite the simplification from the conventional double time G &lt; (t,t′) to single time G &lt; (t,t) used in Eq. (1), the computational cost to obtain G&lt; remains very demanding for the following reasons: 
     (1) Consider A α (ε,t) with a matrix size of N, matrix multiplications  G   r (ω+Δ α ) and {tilde over (G)}(∈) r  in the integrand of Eq. (3) require computational complexity of O(N 3 ) for each time step. As a result, the total computational cost over a period of time is at least O(TN 3 ) where T is the number of time steps. 
     (2) Double integrations in energy space are required for G &lt; . The presence of numerous quasi-resonant states whose energies are close to the real energy axis makes the energy integration in A α  extremely difficult to converge. 
     This problem can be overcome using the CAP method as described in the article J. Driscoll and K. Varga,  Phys. Rev. B  78, 245118 (2008), which is incorporated herein by reference in its entirety. The essence of the CAP method is to replace each semi-infinite lead by a finite region of CAP while keeping the transmission coefficient of the system unchanged. In addition, it is demonstrated in the Zhang article that the first principles result of transient current for molecular junctions obtained from the exact numerical method (non-WBL) and the CAP method are exactly the same. Using the CAP method, the poles of Green&#39;s function can be obtained easily and the spectral function can be calculated analytically using the residue theorem. Expanding the Fermi function using the Pade spectrum decomposition (PSD), as explained more fully in the detailed description of the invention below, further allows for the calculation of the transient current separately in space and time domain making the O(T 0 N 3 ) algorithm possible. See, J. Hu et al.,  J. Chem. Phys.  133, 101106 (2010), which is incorporated herein by reference in its entirety. 
     Achieving the algorithm of the present invention for the transient current calculation can now be demonstrated, i.e., I α (t j ) for j=1, 2, . . . , T. First Eq. (3) is substituted into Eq. (2), and G &lt; (t,t) can be written as 
     
       
         
           
             
               
                 
                   
                     
                       
                         G 
                         &lt; 
                       
                       ⁡ 
                       
                         ( 
                         
                           t 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           i 
                           / 
                           π 
                         
                         ) 
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             B 
                             1 
                           
                           + 
                           
                             ∫ 
                             
                               d 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               ω 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               d 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ω 
                                 ′ 
                               
                               ⁢ 
                               
                                 e 
                                 
                                   
                                     - 
                                     
                                       i 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           ω 
                                           - 
                                           
                                             ω 
                                             ′ 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   ⁢ 
                                   t 
                                 
                               
                               ⁢ 
                               
                                 
                                   B 
                                   2 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     ω 
                                     , 
                                     
                                       ω 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               α 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ∫ 
                               
                                 d 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 ɛ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 d 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ω 
                                   ′ 
                                 
                                 ⁢ 
                                 
                                   e 
                                   
                                     
                                       i 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ω 
                                             ′ 
                                           
                                           - 
                                           ϵ 
                                         
                                         ) 
                                       
                                     
                                     ⁢ 
                                     t 
                                   
                                 
                                 ⁢ 
                                 
                                   f 
                                   ⁡ 
                                   
                                     ( 
                                     ϵ 
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   A 
                                   
                                     1 
                                     ⁢ 
                                     α 
                                   
                                 
                                 ⁢ 
                                 
                                   W 
                                   α 
                                 
                                 ⁢ 
                                 
                                   A 
                                   
                                     2 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     α 
                                   
                                   † 
                                 
                               
                             
                           
                           + 
                           
                             c 
                             . 
                             c 
                             . 
                           
                         
                         ] 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     where,
         B 1 =∫dϵƒ(ϵ)Σ α A 1α W α A 1α   † , B 2 (ω, ω′)=∫dϵƒ(ϵ)Σ α A 2α (ω, ϵ)W α A 2α   † (ω′, ϵ), and W α  is the CAP matrix. In terms of the poles of Green&#39;s function and the Fermi distribution function, which are explained more fully in the detailed description of the invention below, we have:       

     
       
         
           
             
               
                 
                   
                     
                       
                         G 
                         &lt; 
                       
                       ⁡ 
                       
                         ( 
                         
                           t 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           i 
                           / 
                           π 
                         
                         ) 
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             B 
                             1 
                           
                           + 
                           
                             
                               ∑ 
                               nm 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 e 
                                 
                                   
                                     - 
                                     
                                       i 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ϵ 
                                             n 
                                           
                                           - 
                                           
                                             ϵ 
                                             m 
                                             * 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   ⁢ 
                                   t 
                                 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   
                                     
                                       B 
                                       _ 
                                     
                                     2 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         ϵ 
                                         n 
                                       
                                       , 
                                       
                                         ϵ 
                                         m 
                                         * 
                                       
                                     
                                     ) 
                                   
                                 
                                 ++ 
                               
                               ⁢ 
                               
                                 
                                   ∑ 
                                   α 
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     lm 
                                   
                                   ⁢ 
                                   
                                     
                                       e 
                                       
                                         
                                           - 
                                           
                                             i 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 
                                                   ϵ 
                                                   l 
                                                 
                                                 - 
                                                 
                                                   ϵ 
                                                   m 
                                                   * 
                                                 
                                                 + 
                                                 
                                                   Δ 
                                                   α 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         ⁢ 
                                         t 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         f 
                                         _ 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ϵ 
                                             _ 
                                           
                                           l 
                                         
                                         ) 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           B 
                                           _ 
                                         
                                         
                                           3 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           α 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             
                                               ϵ 
                                               _ 
                                             
                                             l 
                                           
                                           , 
                                           
                                             ϵ 
                                             m 
                                             * 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                           
                           + 
                           
                             c 
                             . 
                             c 
                             . 
                             
                               + 
                               
                                 
                                   ∑ 
                                   α 
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     nm 
                                   
                                   ⁢ 
                                   
                                     
                                       e 
                                       
                                         
                                           - 
                                           
                                             i 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 
                                                   ϵ 
                                                   n 
                                                 
                                                 - 
                                                 
                                                   ϵ 
                                                   m 
                                                   * 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         ⁢ 
                                         t 
                                       
                                     
                                     ⁢ 
                                     
                                       f 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ϵ 
                                             n 
                                           
                                           - 
                                           
                                             Δ 
                                             α 
                                           
                                         
                                         ) 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           B 
                                           _ 
                                         
                                         
                                           4 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           α 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ϵ 
                                             n 
                                           
                                           , 
                                           
                                             ϵ 
                                             m 
                                             * 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                           
                           + 
                           
                             c 
                             . 
                             c 
                             . 
                           
                         
                         ] 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     where ε n  and ε m  (n=1, 2, . . . N) is the complex energy of 
               H   neq     -     i   ⁢       ∑   α     ⁢           ⁢     W   α               
in the lower half plane, while {tilde over (∈)} l  are the poles of ƒ(E) using PSD with l=1, . . . N ƒ ; and N ƒ  is the total number of those poles for the adopted Pade approximant.
 
     Within the CAP framework, G &lt;  in Eq. (1) is the lesser Green&#39;s function of the central scattering region excluding the CAP regions. Substituting the second term of Eq. (4) into the first term in Eq. (1), its contribution to current (denoted as I 1 ) is 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             I 
                             1 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           Re 
                           ⁢ 
                           
                             
                               ∑ 
                               nm 
                             
                             ⁢ 
                             
                               
                                 e 
                                 
                                   
                                     - 
                                     
                                       i 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ϵ 
                                             n 
                                           
                                           - 
                                           
                                             ϵ 
                                             m 
                                             * 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   ⁢ 
                                   t 
                                 
                               
                               ⁢ 
                               
                                 Tr 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     
                                       
                                         Γ 
                                         _ 
                                       
                                       α 
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       H 
                                       neq 
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           B 
                                           _ 
                                         
                                         2 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ϵ 
                                             n 
                                           
                                           , 
                                           
                                             ϵ 
                                             m 
                                             * 
                                           
                                         
                                         ) 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         Γ 
                                         _ 
                                       
                                       α 
                                     
                                   
                                   ] 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           ≡ 
                             
                           ⁢ 
                           
                             2 
                             ⁢ 
                             Re 
                             ⁢ 
                             
                               
                                 ∑ 
                                 nm 
                               
                               ⁢ 
                               
                                 
                                   e 
                                   
                                     
                                       - 
                                       
                                         i 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             
                                               ϵ 
                                               n 
                                             
                                             - 
                                             
                                               ϵ 
                                               m 
                                               * 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                     ⁢ 
                                     t 
                                   
                                 
                                 ⁢ 
                                 
                                   M 
                                   nm 
                                 
                               
                             
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     where the matrix M does not depend on time. Thus, the space and time domains have been separated. 
     Denoting a Vandermonde matrix V jk =exp(iε k t j ) with k=1, 2, . . . , N, t j =jdt, j=1, 2, . . . , T where dt is the time interval and I 1 (t j )=[V t (M+M † )V*] jj . Using this approach, I L  is finally obtained. This calculation is more fully explained in the detailed description below: 
     
       
         
           
             
               
                 
                   
                     
                       
                         I 
                         L 
                       
                       ⁡ 
                       
                         ( 
                         
                           t 
                           j 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         I 
                         
                           0 
                           ⁢ 
                           L 
                         
                       
                       + 
                       
                         
                           [ 
                           
                             
                               V 
                               t 
                             
                             ⁢ 
                             
                               M 
                               1 
                             
                             ⁢ 
                             
                               V 
                               * 
                             
                           
                           ] 
                         
                         jj 
                       
                       + 
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 
                                   α 
                                   = 
                                   L 
                                 
                                 , 
                                 R 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 [ 
                                 
                                   
                                     V 
                                     t 
                                   
                                   ⁢ 
                                   
                                     M 
                                     
                                       2 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       α 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       V 
                                       _ 
                                     
                                     α 
                                     * 
                                   
                                 
                                 ] 
                               
                               jj 
                             
                           
                           + 
                           
                             c 
                             . 
                             c 
                             . 
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     where {tilde over (V)} αjk =exp(i({tilde over (ϵ)} k +Δ α )t j ) is a T×N ƒ  matrix, M 1  is a N×N matrix while M 2  is a N×N ƒ  matrix. Since ε k  is the complex energy in the lower half plane, V jk  goes to zero at large j. Hence I 0L  is the long time limit of the transient current which can be calculated using the Landauer Buttiker formula. The time dependent part of the transient current can be separated into a real space calculation (calculation of M 1  and M 2α ) and then a matrix multiplication involving time. At room temperatures the Fermi function can be accurately approximated by 15 or 20 Pade approximants. Hence the calculation of [V t M 1 V*] jj +(Σ α [V t M 2α V α *] jj +c.c.) can be combined to give TN 2  computational complexity. 
     The computational complexity of this algorithm (denoted as algorithm I) can now be examined. By counting the number of matrix multiplication, the computational complexity of the real space calculations can be estimated to be 50N 3 . Therefore the total computational complexity is 50N 3 +TN 2 . At this stage, the algorithm is not O(1) yet. In the detailed description below it is shown that matrix multiplication V t M, where M is M 1  or M 2α , can be done using the FMM and FFT (denoted as algorithm II). This reduces the computational complexity of V t M from TN 2  to T log 2 N. Hence for T&lt;N 2 , the computational complexity is 50N 3 +N 2  log 2 N. For T&gt;N 2 , the scaling is 50N 3 +T log 2 N. However, for large T, the physics comes into play. Since ε j  is the complex energy of the resonant state, V jT =exp(−iε j dtT) decays quickly to zero before T=N 2 . For a graphene nanoribbon with N=10 4  (see details below), the maximum value of V jT =exp(−iε j dtT) is 10 −3  when T=N and dt=1 fs. Consequently all of the matrix elements are zero for T=10N. Hence for large systems, the chance to go beyond T=N 2  is small. In this sense, algorithm II is an order O(1) algorithm. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The patent or application file contains at least one drawing executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee. 
       The foregoing and other objects and advantages of the present invention will become more apparent when considered in connection with the following detailed description and appended drawings in which like designations denote like elements in the various views, and wherein: 
         FIG. 1A  shows the configuration of a gated graphene nanoribbon and a voltage applied to it over time and  FIG. 1B  shows the transient current of the zigzag graphene nanoribbon for a system of 600 atoms for the present invention and the Zhang method; 
         FIG. 2  shows the scaling of computation time versus the number of computations N for the prior art Zhang method and the Algorithm I of the method according to the present invention; 
         FIG. 3  shows the scaling of computational time against time t for N equal to 10,200, time step dt=1 fs; 
         FIG. 4  shows a graph of the typical behavior of transient current, wherein the inset is the long time behavior between 17 ps to 18 ps; 
         FIG. 5  is a graph of the transmission coefficient of a zigzag graphene nanoribbon for a system of 10,000 atoms calculated by 30 layers of CAP and by exact numerical solution; 
         FIG. 6  shows the distribution of (1/ω T ) j  on the complex plane; 
         FIG. 7  shows the distribution of d on the complex plane; 
         FIG. 8  illustrates the transient current calculated by Algorithm I, Algorithm IIa and Algorithm IIb; and 
         FIG. 9  is a flow chart showing the process for the calculation of the algorithm according to the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     First principles transient current calculation is essential to the study of the response time and to capture the peak transient current for preventing the melt down of nano-chips in nano-electronics. For a period of time T, its calculation is known to be extremely time consuming with the best scaling being TN 3  where N is the dimension of the device. The dynamical response of the system is usually probed by sending a step-like pulse and monitoring its transient behavior. 
     The present invention is directed to a new algorithm for calculating the transient current of a system, which requires much less computational time than the prior art.  FIG. 9  shows a flow chart of the method for calculating the algorithm of the present invention. It can be carried out on a computer workstation as part of the design of a nano-device. 
     Generally speaking, the algorithm provides an O(1) computational method for obtaining the transient response of current I(t) over the entire user-defined time period under suitable conditions. The input parameters for this algorithm include Hamiltonians of the open quantum system before and after the transient process denoted as H eq  and H neq . These Hamiltonians, whether based on atomistic first-principle density functional theory (DFT) or tight-binding methods, can be adopted at will for the system of interest. Nonetheless, complex absorbing potential (CAP) is required to represent the self-energy of the leads of the device. Subsequently, corresponding eigenstate and energy can be generated and fed into the algorithm. Additionally, Fermi function is expanded using Pade spectrum decomposition (PSD). 
     It is only possible to construct the particular exact equation of transient current which can be calculated separated in space and time domains by using the mentioned form of input ingredients. Once such an equation is constructed, whether for the case for step-up, step-down bias or other similar classes of transient response, so that I(t) is a function of I o , V m (t) and M n  for some m and n where V m (t) are Vandemonde matrices and I o  and M n  are time independent matrices. Once the required Vandemonde matrices and M n  are constructed, fast multi pole method (FMM) and fast Fourier transform (FFT) are used to calculate the matrix multiplication between them. Eventually, I(t) can be obtained by summing up the contribution due to I o , V m (t) and M n . 
     In step  901  of  FIG. 9  the process begins with input preparation. This includes step  901 A, which involves forming Preliminary Input quantities H eq , H neq  (From first-principle (DFT), TB, etc) and Self energy of leads (from CAP). In step  901 B eigenstates and eigen-energy are generated. This input information is then directed to step  902 . In step  902  construction is performed on the exact equation of transient current based on NEGF formalism that is organized into the general form of I(t)=l t (I o , V m (t), M n ) such that it is a function composed of time dependent Vandermonde matrices V m  and other space dependent matrices M n . Also, there is an input from step  903 , i.e., Fermi functions (from the PSD method) to step  902 . 
     The results of step  902  are then reviewed in step  904  to see if they contain time dependent components. If the answer is NO, the process moves to step  905 . In step  905  the process computes and constructs space dependent matrices by an optimized matrix multiplication process. From step  905  the process goes to step  906  where the FMM and FFT methods are used for computing the multiplication of V m  and M n . 
     If the result of step  904  is YES, the process moves to step  907  where Vandermonde matrices are prepared before moving to step  906 . The results in both step  905  and  906  are summed in Step  908 . The summed results are directed to output step  909 , where the complete transient response I(t) over the user-defined time period is generated. 
     To demonstrate the power of the algorithm according to the present invention, the transient current in a graphene nanoribbon is calculated. Graphene is a well-known intrinsic 2D material with many exotic properties. See, A. H. Castro Neto et al.,  Rev. Mod. Phys.  81, 109 (2009) and Y. Zhang et al.,  Nature,  438, 201-204 (2005), which are incorporated herein by reference in their entirety. Studies of its transient behavior in response to a step-like pulse have been reported in the literature. See the Stefanucci article and E. Perfetto et al.,  Phys. Rev. B  82, 035446 (2010) and Y. O. Klymenko et al.,  Eur. Phys. J. B  69, 383-388 (2009), which are both incorporated herein by reference in their entirety. 
     The algorithm of the present invention was tested on a gated graphene nanoribbon at room temperature using the tight-binding (TB) Hamiltonian given by 
     
       
         
           
             
               
                 
                   
                     
                       H 
                       ^ 
                     
                     = 
                     
                       
                         
                           - 
                           
                             h 
                             0 
                           
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               
                                 &lt; 
                                 i 
                               
                               , 
                               
                                 j 
                                 &gt; 
                               
                             
                           
                           ⁢ 
                           
                             
                               
                                 c 
                                 ^ 
                               
                               i 
                               † 
                             
                             ⁢ 
                             
                               
                                 c 
                                 ^ 
                               
                               j 
                             
                           
                         
                       
                       - 
                       
                         q 
                         ⁢ 
                         
                           
                             ∑ 
                             i 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               [ 
                               
                                 
                                   
                                     V 
                                     1 
                                   
                                   ⁢ 
                                   
                                     θ 
                                     ⁡ 
                                     
                                       ( 
                                       t 
                                       ) 
                                     
                                   
                                 
                                 + 
                                 
                                   V 
                                   
                                     g 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     1 
                                     ⁢ 
                                     i 
                                   
                                 
                                 + 
                                 
                                   V 
                                   
                                     g 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     i 
                                   
                                 
                               
                               ] 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 c 
                                 ^ 
                               
                               i 
                               † 
                             
                             ⁢ 
                             
                               
                                 c 
                                 ^ 
                               
                               i 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     where ĉ i   † (ĉ i ) is the creation (annihilation) operator at site i and h 0 =2.7 eV being the nearest hopping constant. Here V(x)=V L +(V R −V L )x/L is the potential landscape due to the external bias with V R =−V L =0.54V, and V g1  and V g2  being the gate voltages in regions S 1  and S 2 , respectively. 
     First it is confirmed that the transient current calculated using the new method is the same as that of the Zhang reference. Using 30 layers of CAP, the transmission coefficient versus the energy was calculated and it showed good agreement with the exact solution.  FIG. 5  provides a comparison for a graphene nanoribbon with N=10,000. In  FIG. 5  the solid line (T S ) is the exact numerical result using self-energy of the lead and the dashed line (T CAP ) is from CAP. This also ensures the correct steady state current. For the transient current, excellent agreement is also obtained between the algorithm of the present invention and that of the Zhang reference (See  FIG. 2 ). It should be noted that in the presence of gates, the “on-off” time of graphene is shortened in comparison to un-gated graphene which has a long oscillating current as reported in the Stefannucci article. Also the transient current is calculated for a graphene nanoribbon with size of N=10 4  and T=20,000 with each time step 1 fs. See  FIG. 5 . 
     Now testing of the scaling of the algorithm of the present invention can be achieved by calculating the transient current for nanoribbons with different system sizes ranging from 600 to 10,200 atoms. The first test is with algorithm I. The computational time for the transient current for 3 time steps compared against system sizes N is shown in  FIG. 2 . In  FIG. 5  the data is fitted using 50N 3 +TN 2  with very good agreement showing TN 2  scaling for the time-dependent part. For comparison,  FIG. 5  also shows a plot of the computation time using the method in the Zhang reference. It was found that the number of energy points N E  depends on the spectrum of resonant states of the system. For graphene nanoribbons with 600 atoms, N E =6000 was used to converge the integral over a Fermi function.  FIG. 2  shows that a speed up factor of 1000T is achieved at N=2400. The scaling is shown in  FIG. 3 , from which it can be seen that for T&lt;N the computational time is almost independent of the number of time steps. 
     Now algorithm II, which reduces the scaling TN 2  further, can be examined. Notice that the scaling TN 2  comes from matrix multiplication involving Vandermonde matrix V t M 1 . The fast algorithm is available to speed up the calculation involving a structured matrix, such as the Vandermonde matrix. As discussed in detail below the FMM as in the Rokhlin and Song articles and FFT can be used to carry out the same matrix multiplication using only c 3 N 2  log 2 N operations provided that T&lt;N 2 . Here the coefficient c 3  is a large constant that depends only on the tolerance of the calculation τ and the setup of FMM. The theoretical estimate of this coefficient is about 40 log 2 (1/τ) where τ is the tolerance in the FMM calculation, which used τ=10 −4 . See N. Yarvin et al.,  Anal.  36, 629 (1999), which is incorporated herein by reference in its entirety. When implementing FMM, this coefficient is in general larger than the theoretical one. 
     To test algorithm II, the transient current is calculated for N=10 4  and T=10 8  as explained in detail below, using FMM and FFT. Denote t 1  the CPU time needed for the spatial calculation (50N 3 ), t 2  is the time needed for the temporal part (matrix multiplication in Eq. (7)) using, e.g., a Xeon X5650 workstation with 12 cores and a frequency of 2.67 GHz. The result t 1 =3500s is obtained using 12 cores and t 1 =33800s using a single core so the efficiency of multithreading is about 80%. For an FMM calculation, multithreading could be very inefficient so a single core has been used to perform the calculation. It was found t 2 =3400s for T=10 8  using a single core, as shown below in the detailed computational analysis and numerical calculation. It was found that for T=10 8  the time spent in the time dependent part is about one tenth of the time of the independent calculation. This confirms that the method of the present invention uses an algorithm of order O(1) as long as T&lt;N 2 . It should be pointed out that algorithm II is directed to the calculation of the transient current I(t) with time steps T=N 2  at one shot with scaling N 2  log 2 N. This scaling remains if I(t) with the number of time step less than N 2  is desired. 
       FIG. 2  shows the scaling of N against computation time at T=3 (each time step is 1 fs). The fitted curve, which is in the form of 50N 3 +TN 2 , is in good agreement with the calculated results The Y-axis is on the right. In order compare the present invention to the performance reported in the Zhang reference, 6000 energy points were used for integration using the Y-axis on the left. 
       FIG. 3  illustrates the scaling of t against CPU time for N=10,200 (t=100 fs corresponds to T=100) using algorithm I. The left hand side uses an exponential scale in t and the right hand side uses a linear scale in t.  FIG. 3  shows that at extremely large data points, e.g., ranges over 10 thousands points, the computational time is proportional to T. 
     Since the algorithm of the present invention is based on the NEGF-CAP formalism, it can be extended to the NEGF-DFT-CAP formalism which performs the first principles calculation. In fact, the NEGF-DFT-CAP method has already been successfully implemented in the first principles transient current calculation as shown in the Zhang reference, which gives exactly the same result as that of NEGF-DFT. With the fast algorithm at hand, many applications can be envisaged. For instance, the transient spin current (related to spin transfer torque) using the NEGF-DFT-CAP formalism has been carried out for planar structures where k-sampling in the first Brillouin zone is needed. It is straightforward to include k-sampling in the method of the present invention. It is also possible to extend this method to the case where electron-phonon interaction in the Born approximation as well as other dephasing mechanisms are present. Finally, first principles transient photo-induced current on two dimensional layered materials can be calculated using the method of the present invention. 
     Some of the details of the calculations presented above are given here. 
     Pade Approximant 
     Brute force integration over the Fermi function along the real energy axis to obtain G &lt; (t,t) may need thousands of energy points to converge, which is very inefficient. To obtain an accurate result while reducing the cost, fast converging Pade spectrum decomposition (PSD) is used for the Fermi function ƒ in Eq. (4) above, so that the residue theorem can be applied. Using [n−1/n] PSD scheme with the Pade approximant accurate up to O((ε/kT) 4n-1 ), Fermi function ƒ can be expressed as 
     
       
         
           
             
               
                 
                   
                     
                       f 
                       ⁡ 
                       
                         ( 
                         ɛ 
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         2 
                       
                       - 
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             1 
                           
                           n 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             2 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               η 
                               j 
                             
                             ⁢ 
                             βɛ 
                           
                           
                             
                               
                                 ( 
                                 βɛ 
                                 ) 
                               
                               2 
                             
                             + 
                             
                               ξ 
                               j 
                               2 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     where ξ j  and η j  are two set of constants that can be calculated easily. Using the PSD scheme analytic form of G &lt;  in Eq. (4) can be obtained using the residue theorem. See J. Hu et al.,  J. Chem. Phys.  133, 101106 (2010), which is incorporated herein by reference in its entirety. 
     Calculation of the Spectral Function 
     The terms {tilde over (G)} r (ϵ) and  G   r (ε), the equilibrium and non-equilibrium retarded Green&#39;s functions, respectively, can be expressed in terms of their eigen-functions by solving the following eigen-equations for H eq  and H neq , i.e.,
 
( H   eq   −iW )ψ n   0 =ϵ n   0 ψ n   0 ,
 
( H   eq   +iW   † )ϕ n   0 =ϵ n   0 ϕ n   0 ,  (10)
 
     where 
             W   =       ∑   α     ⁢           ⁢     W   α             
and similar equations can be defined for H neq . See the Zhang reference. Using the eigen-functions of H eq −iW and H neq −iW, we have
 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           G 
                           ~ 
                         
                         r 
                       
                       ⁡ 
                       
                         ( 
                         ϵ 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           [ 
                           
                             ϵ 
                             - 
                             
                               H 
                               eq 
                             
                             + 
                             iW 
                           
                           ] 
                         
                         
                           - 
                           1 
                         
                       
                       = 
                       
                         
                           ∑ 
                           n 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             
                                
                               
                                 ψ 
                                 n 
                                 0 
                               
                               〉 
                             
                             ⁢ 
                             
                               〈 
                               
                                 ϕ 
                                 n 
                                 0 
                               
                                
                             
                           
                           
                             ( 
                             
                               ϵ 
                               - 
                               
                                 ϵ 
                                 n 
                                 0 
                               
                               + 
                               
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   0 
                                   + 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         G 
                         _ 
                       
                       r 
                     
                     ⁡ 
                     
                       ( 
                       ϵ 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           ϵ 
                           - 
                           
                             H 
                             neq 
                           
                           + 
                           iW 
                         
                         ] 
                       
                       
                         - 
                         1 
                       
                     
                     = 
                     
                       
                         ∑ 
                         n 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           
                             
                                
                               
                                 ψ 
                                 n 
                               
                               〉 
                             
                             ⁢ 
                             
                               〈 
                               
                                 ϕ 
                                 n 
                               
                                
                             
                           
                           
                             ( 
                             
                               ϵ 
                               - 
                               
                                 ϵ 
                                 n 
                               
                               + 
                               
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   0 
                                   + 
                                 
                               
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     Performing an integral over ω using the residue theorem, the analytic solution of A α  is obtained 
     
       
         
           
             
               
                 
                   
                     
                       A 
                       α 
                     
                     ⁡ 
                     
                       ( 
                       
                         ϵ 
                         , 
                         t 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         n 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           
                              
                             
                               ψ 
                               n 
                             
                             〉 
                           
                           ⁢ 
                           
                             〈 
                             
                               ϕ 
                               n 
                             
                              
                           
                         
                         
                           ϵ 
                           + 
                           
                             Δ 
                             α 
                           
                           - 
                           
                             ϵ 
                             n 
                           
                           + 
                           
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               0 
                               + 
                             
                           
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         n 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           
                             
                               e 
                               
                                 
                                   i 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       ϵ 
                                       + 
                                       
                                         Δ 
                                         α 
                                       
                                       - 
                                       
                                         ϵ 
                                         n 
                                       
                                     
                                     ) 
                                   
                                 
                                 t 
                               
                             
                             ⁢ 
                             
                                
                               
                                 ψ 
                                 n 
                               
                               〉 
                             
                             ⁢ 
                             
                               〈 
                               
                                 ϕ 
                                 n 
                               
                                
                             
                           
                           
                             ϵ 
                             - 
                             
                               ϵ 
                               n 
                             
                             + 
                             
                               i 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 0 
                                 + 
                               
                             
                           
                         
                         × 
                         
                             
                           
                               
                           
                           ⁢ 
                           
                             
                               [ 
                               
                                 
                                   
                                     Δ 
                                     α 
                                   
                                   
                                     ϵ 
                                     + 
                                     
                                       Δ 
                                       α 
                                     
                                     - 
                                     
                                       ϵ 
                                       n 
                                     
                                     + 
                                     
                                       i 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         0 
                                         + 
                                       
                                     
                                   
                                 
                                 - 
                                 
                                   Δ 
                                   ⁢ 
                                   
                                     
                                       ∑ 
                                       l 
                                     
                                     ⁢ 
                                     
                                       
                                         
                                            
                                           
                                             ψ 
                                             l 
                                             0 
                                           
                                           〉 
                                         
                                         ⁢ 
                                         
                                           〈 
                                           
                                             ϕ 
                                             l 
                                             0 
                                           
                                            
                                         
                                       
                                       
                                         ( 
                                         
                                           ϵ 
                                           - 
                                           
                                             ϵ 
                                             l 
                                             0 
                                           
                                           + 
                                           
                                             i 
                                             ⁢ 
                                             
                                                 
                                             
                                             ⁢ 
                                             
                                               0 
                                               + 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     where Δ=H neq −H eq . 
     Calculation of the Lesser Green&#39;s Function 
     In Eq. (5) using residue theorem the involved terms are defined as 
     
       
         
           
             
                 
             
             ⁢ 
             
               
                 
                   B 
                   _ 
                 
                 2 
               
               = 
               
                 
                   
                     
                       - 
                       4 
                     
                     ⁢ 
                     
                       
                         π 
                         2 
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               B 
                               2 
                             
                             ⁡ 
                             
                               ( 
                               
                                 ω 
                                 , 
                                 
                                   ω 
                                   ′ 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             ( 
                             
                               ω 
                               - 
                               
                                 ϵ 
                                 n 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             ( 
                             
                               
                                 ω 
                                 ′ 
                               
                               - 
                               
                                 ϵ 
                                 m 
                                 * 
                               
                             
                             ) 
                           
                         
                         ] 
                       
                     
                   
                   ⁢ 
                   
                     ❘ 
                     
                       
                         ω 
                         = 
                         
                           ϵ 
                           n 
                         
                       
                       , 
                       
                         
                           ω 
                           ′ 
                         
                         = 
                         
                           ϵ 
                           m 
                           * 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       B 
                       _ 
                     
                     
                       3 
                       ⁢ 
                       α 
                     
                   
                 
                 = 
                 
                   
                     
                       
                         - 
                         2 
                       
                       ⁢ 
                       π 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           iA 
                           
                             1 
                             ⁢ 
                             α 
                           
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               ϵ 
                               ~ 
                             
                             l 
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         
                           W 
                           α 
                         
                         ⁡ 
                         
                           [ 
                           
                             
                               
                                 A 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                                 † 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     ω 
                                     ′ 
                                   
                                   , 
                                   
                                     
                                       ϵ 
                                       ~ 
                                     
                                     l 
                                   
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   ω 
                                   ′ 
                                 
                                 - 
                                 
                                   ϵ 
                                   m 
                                   * 
                                 
                               
                               ) 
                             
                           
                           ] 
                         
                       
                     
                     ⁢ 
                     
                       ❘ 
                       
                         
                           ω 
                           ′ 
                         
                         = 
                         
                           ϵ 
                           m 
                           * 
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         B 
                         _ 
                       
                       
                         4 
                         ⁢ 
                         α 
                       
                     
                   
                   = 
                   
                     
                       - 
                       4 
                     
                     ⁢ 
                     
                       
                         π 
                         2 
                       
                       [ 
                       
                         
                           
                             
                               
                                 A 
                                 
                                   1 
                                   ⁢ 
                                   α 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 ϵ 
                                 ) 
                               
                             
                             ⁢ 
                             
                               W 
                               α 
                             
                             ⁢ 
                             
                               
                                 A 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                                 † 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     ω 
                                     ′ 
                                   
                                   , 
                                   ϵ 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   ω 
                                   ′ 
                                 
                                 - 
                                 
                                   ϵ 
                                   m 
                                   * 
                                 
                               
                               ) 
                             
                             × 
                             
                                 
                               
                                 ( 
                                 
                                   ϵ 
                                   - 
                                   
                                     ϵ 
                                     n 
                                   
                                   + 
                                   
                                     Δ 
                                     α 
                                   
                                 
                                 ) 
                               
                               ] 
                             
                           
                           ⁢ 
                           
                             ❘ 
                             
                               
                                 ϵ 
                                 = 
                                 
                                   
                                     ϵ 
                                     n 
                                   
                                   - 
                                   
                                     Δ 
                                     α 
                                   
                                 
                               
                               , 
                               
                                 
                                   ω 
                                   ′ 
                                 
                                 = 
                                 
                                   ϵ 
                                   m 
                                   * 
                                 
                               
                             
                           
                           ⁢ 
                           
                             
 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             f 
                             _ 
                           
                         
                         = 
                         
                           
                             2 
                             ⁢ 
                             π 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               i 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     f 
                                     ⁡ 
                                     
                                       ( 
                                       ϵ 
                                       ) 
                                     
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       ϵ 
                                       - 
                                       
                                         
                                           ϵ 
                                           ~ 
                                         
                                         l 
                                       
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                           
                           ⁢ 
                           
                             ❘ 
                             
                               ϵ 
                               = 
                               
                                 
                                   ϵ 
                                   _ 
                                 
                                 l 
                               
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Calculation of the Transient Current 
     Starting from Eq. (1) and in analogue to Eq. (6), the expressions of the current in Eq. (7) can be obtained as follows: 
     
       
         
           
             
               
                 I 
                 
                   0 
                   ⁢ 
                   L 
                 
               
               ⁡ 
               
                 ( 
                 
                   t 
                   j 
                 
                 ) 
               
             
             = 
             
               2 
               ⁢ 
               Re 
               ⁢ 
               
                   
               
               ⁢ 
               
                 Tr 
                 ⁡ 
                 
                   [ 
                   
                     
                       i 
                       π 
                     
                     ⁢ 
                     
                       
                         Γ 
                         _ 
                       
                       L 
                     
                     ⁢ 
                     
                       H 
                       neq 
                     
                     ⁢ 
                     
                       B 
                       1 
                     
                     ⁢ 
                     
                       
                         Γ 
                         _ 
                       
                       L 
                     
                   
                   ] 
                 
               
             
           
         
       
       
         
           
             
               M 
               1 
             
             = 
             
               Re 
               ⁢ 
               
                   
               
               ⁢ 
               
                 Tr 
                 ⁡ 
                 
                   [ 
                   
                     
                       i 
                       π 
                     
                     ⁢ 
                     
                       
                         
                           Γ 
                           _ 
                         
                         L 
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             2 
                             ⁢ 
                             
                               H 
                               neq 
                             
                           
                           - 
                           
                             ( 
                             
                               
                                 ϵ 
                                 n 
                               
                               - 
                               
                                 ϵ 
                                 m 
                                 * 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             B 
                             _ 
                           
                           2 
                         
                         + 
                         
                           
                             ∑ 
                             α 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               f 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     ϵ 
                                     n 
                                   
                                   - 
                                   
                                     Δ 
                                     α 
                                   
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               
                                 B 
                                 _ 
                               
                               
                                 4 
                                 ⁢ 
                                 α 
                               
                             
                           
                         
                       
                       ) 
                     
                     ⁢ 
                     
                       
                         Γ 
                         _ 
                       
                       L 
                     
                   
                   ] 
                 
               
             
           
         
       
       
         
           
             
               M 
               
                 2 
                 ⁢ 
                 α 
               
             
             = 
             
               Re 
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   Tr 
                   ⁡ 
                   
                     [ 
                     
                       
                         i 
                         π 
                       
                       ⁢ 
                       
                         
                           
                             Γ 
                             _ 
                           
                           L 
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               2 
                               ⁢ 
                               
                                 H 
                                 neq 
                               
                             
                             - 
                             
                               ( 
                               
                                 
                                   
                                     ϵ 
                                     _ 
                                   
                                   l 
                                 
                                 - 
                                 
                                   ϵ 
                                   m 
                                   * 
                                 
                                 + 
                                 
                                   Δ 
                                   o 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             f 
                             ⁡ 
                             
                               ( 
                               
                                 ϵ 
                                 m 
                                 * 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               B 
                               _ 
                             
                             
                               3 
                               ⁢ 
                               α 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         
                           Γ 
                           _ 
                         
                         L 
                       
                     
                     ] 
                   
                 
                 . 
               
             
           
         
       
     
     The expression of transient current I R (t) is similar to Eq. (7). 
     Transient Current for a Graphene Nanoribbon of System Size N=10 4    
     A calculation was performed on transient current through a zigzag graphene nanoribbon of 10,000 atoms with T=20,000 time steps (each time step is 1 fs). The width of the system is two unit cells (16 atoms) while the length of the system is 625 unit cells. Two gate voltages of 2.2V were applied so that the system is in the tunneling regime. The bias voltage is v L =v R =0.5V. From  FIG. 4 , it can be seen that a typical behavior of transient current with the current shooting up initially and then decreasing oscillations to the long time limit (the numerical results using FMM show that 100 ps is needed to reach the dc limit, which is shown as a dashed line). The oscillatory behavior is due to resonant states in the system. This test was at a temperature of 300° K. The inset is the long time behavior between 17 ps to 18 ps. 
       FIG. 5  shows the transmission coefficient of the zigzag graphene nanoribbon for a system of 10,000 atoms. The solid line (T S ) is the exact numerical result using self-energy of the lead and the dashed line (T CAP ) is from CAP. Thus,  FIG. 5  shows a comparison between the exact numerical result of the transmission coefficient using the self-energy of the lead and that of CAP. There is very close agreement. 
     Fast Multipole Method 
     The fast multipole method has been widely used and has been ranked top 10 best algorithms in 20th Century. See, V. Rokhlin,  J. Comput. Phys.  60, 187-207 (1985); J. Song, C. C. Lu, and W. C. Chew,  IEEE trans. Antennas Propagat.  45, 1488-1493 (1997); and B. A. Cipra,  SIAM News,  33(4), 2 (2000), which are incorporated herein by reference in their entirety. It is extremely efficient for large N. The following quantity is then calculated: 
     
       
         
           
             
               
                 
                   
                     
                       I 
                       ⁡ 
                       
                         ( 
                         t 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           n 
                           , 
                           m 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           exp 
                           ⁡ 
                           
                             ( 
                             
                               
                                 - 
                                 i 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ɛ 
                                 n 
                               
                               ⁢ 
                               t 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           M 
                           nm 
                         
                         ⁢ 
                         
                           exp 
                           ⁡ 
                           
                             ( 
                             
                               i 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ɛ 
                                 m 
                                 * 
                               
                               ⁢ 
                               t 
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     where the matrix M can be expressed in terms of vectors as M=(c 0 , c 1 , . . . , c N-1 ) and V nj =exp(−iε n t j ) is a Vandermonde matrix with t j =jdt and j=1, 2, . . . T. Eq. (14) is of the form V t MV* where t stands for transpose. In the following, an outline of how to calculate V t c where c is a vector of N components is given. 
     Setting a j =exp(−iε j dt) and denoting T the number of time steps. Then b=V t c is equivalent to 
               b   n     =       ∑     j   =   0       N   -   1       ⁢           ⁢           c   j     ⁡     (     a   j     )       n     .             
A direct computation shows that the entries of b=V t c are the first T coefficients of the Taylor expansion of
 
                       S   ⁡     (   x   )       =         ∑     j   =   0       N   -   1       ⁢       c   j       1   -       a   j     ⁢   x           =         ∑   n   ∞     ⁢           ⁢       ∑     j   =   0       N   -   1       ⁢         c   j     ⁡     (       a   j     ⁢   x     )       n         =       ∑   n     ⁢           ⁢       b   n     ⁢     x   n               ,           (   15   )               where  b   n =Σ j=0   N-1   c   j ( a   j ) n .
 
     Denoting  S (x)=Σ n=0   T-1 b n x n  and setting x=ω T   l  with ω T =exp(i2π/T) it can be used to calculate  − S(ω T   l ) which is the Fourier transform of b n , 
     
       
         
           
             
               
                 
                   
                     S 
                     ⁡ 
                     
                       ( 
                       
                         ω 
                         T 
                         l 
                       
                       ) 
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           n 
                           = 
                           0 
                         
                         
                           T 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           c 
                           j 
                         
                         ⁢ 
                         
                           a 
                           j 
                           n 
                         
                         ⁢ 
                         
                           ω 
                           T 
                           nl 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         c 
                         j 
                       
                       ⁢ 
                       
                         
                           1 
                           - 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   j 
                                 
                                 ⁢ 
                                 
                                   ω 
                                   T 
                                   l 
                                 
                               
                               ) 
                             
                             T 
                           
                         
                         
                           1 
                           - 
                           
                             
                               a 
                               j 
                             
                             ⁢ 
                             
                               ω 
                               T 
                               l 
                             
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     = 
                       
                     ⁢ 
                     
                       
                         ω 
                         T 
                         
                           - 
                           l 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             
                               c 
                               j 
                             
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   a 
                                   j 
                                   T 
                                 
                               
                               ) 
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   1 
                                   / 
                                   
                                     ω 
                                     T 
                                   
                                 
                                 ) 
                               
                               l 
                             
                             - 
                             
                               a 
                               j 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
             
           
         
       
     
     where ω T   T =1 is used. Note that the fast multipole method (FMM) aims to calculate 
               v   l     =       ∑   j     ⁢           ⁢       c   j     /     (       x   l     -     a   j       )               
with O(N) operations instead of N 2  operations. Hence  S (ω T   l ) can be obtained using FMM, from which b n  can be calculated using FFT.
 
     Now the computational complexity for T≤N can be estimated. For FMM the value κ 1 max(T,N) operations are needed where κ 1  is about 40 log 2 (1/τ) with τ the tolerance. See N. Yarvin and V. Rokhlin,  SIAM J. Numer. Anal.  36, 629 (1999), which is incorporated herein by reference in its entirety. For FFT the computational complexity is at most κ 2 N log 2 N, where κ 2  is a coefficient for FFT calculation. To compute V t M where M has N vectors, V t c is calculated N times. Hence the total computational complexity is κ 1 N 2 +κ 2 N 2  log 2 N. This algorithm is denoted as algorithm IIa while the algorithm for T&lt;N 2  discussed below is denoted as algorithm IIb. 
     For very large T up to T=N 2  (if N=10 4  and T=10 8 ), it can be shown that the computational complexity is κ 1 N 2 +2κ 2 N 2  log 2 N. In fact, it is easy to see that I(t j ) defined in Eq. (6) is the first T coefficients of the Taylor expansion of 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           S 
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ∑ 
                             
                               n 
                               , 
                               
                                 m 
                                 = 
                                 0 
                               
                             
                             
                               N 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               M 
                               nm 
                             
                             
                               1 
                               - 
                               
                                 
                                   a 
                                   n 
                                 
                                 ⁢ 
                                 
                                   a 
                                   m 
                                   * 
                                 
                                 ⁢ 
                                 x 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ∑ 
                             j 
                             ∞ 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 n 
                                 , 
                                 
                                   m 
                                   = 
                                   0 
                                 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 
                                   
                                     M 
                                     nm 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         n 
                                       
                                       ⁢ 
                                       
                                         a 
                                         m 
                                         * 
                                       
                                     
                                     ) 
                                   
                                 
                                 i 
                               
                               ⁢ 
                               
                                 
                                   x 
                                   j 
                                 
                                 ( 
                                 17 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               ∑ 
                               j 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               I 
                               ⁡ 
                               
                                 ( 
                                 
                                   t 
                                   j 
                                 
                                 ) 
                               
                             
                           
                         
                         ; 
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     where a n =exp(−iε n dt). Now two new vectors u and d can be defined which have N 2  components with u t =(c 0   t , c 1   t , . . . , c N-1   t ) (recall the definition M=(c 0 , c 1 , . . . , c N-1 )) and d t =(a* 0 a t , a* 1 a t , . . . , a* N-1 a t ), where once again t stands for transpose. With the new vectors defined, S(x) in Eq. (16) is expressed as 
     
       
         
           
             
               
                 
                   
                     
                       S 
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           
                             N 
                             2 
                           
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           u 
                           j 
                         
                         
                           1 
                           - 
                           
                             
                               d 
                               j 
                             
                             ⁢ 
                             x 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
     which is exactly the same form as Eq. (15). The only difference is that c and a in Eq. (15) have N components and S has to be calculated N times while u and d in Eq. (18) have N 2  components and S can be calculated according to Eq. (18) just once. Therefore the computational complexity is κ 1 N 2 +κ 2 N 2  log 2 N 2 . If T=nN with n=1, 2, . . . N, it is not difficult to show that the computational complexity is κ 1 TN/n+κ 2 T(N/n)log 2 (nN)=κ 1 N 2 +κ 2 N 2  log 2 (nN). 
     To summarize, the computational complexity of Eq. (14) is κ 1 N 2 +2κ 2 N 2  log 2 N for T&lt;N 2 . It is easy to show that for T&gt;N 2  the scaling is κ 1 N 2 +2κ 2 T log 2 N. However, for large T, the physics comes into play. Since a j =exp(−iε j dt) with ε j  the energy of resonant state, a j   T  quickly decays to zero before T=N 2  and hence no need to go up for T&gt;N 2 . 
     Algorithm II was tested numerically for a system with N=10 4  and T=10 8 . The configuration of the system is the same as that which appears in  FIG. 1 , except the width W of the system is now 17 times wider with a total of 10200˜10 4  atoms. Each time step is 0.012 fs. The computed transient current using Algorithm I and II are shown in  FIG. 8 . The purpose of this calculation is to test the computational complexity only. All that needs to be done is to compute, 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                             
                           - 
                         
                         ⁢ 
                         S 
                       
                       ⁡ 
                       
                         ( 
                         
                           ω 
                           T 
                           l 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ω 
                         T 
                         
                           - 
                           l 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             0 
                           
                           
                             
                               N 
                               2 
                             
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             
                               u 
                               j 
                             
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   d 
                                   j 
                                   T 
                                 
                               
                               ) 
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   1 
                                   / 
                                   
                                     ω 
                                     T 
                                   
                                 
                                 ) 
                               
                               l 
                             
                             - 
                             
                               d 
                               j 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     using FMM and then taking FFT to obtain I(t j ) where u j  and d j  have been defined just before Eq. (18). Note that u j  has been obtained in the time independent calculation. If (1/ω T ) j  and d j  in Eq. (19) are uniformly distributed on the complex plane, the FMM can be done much faster. However, as shown in  FIG. 6  and  FIG. 7 , the unit distribution of (1/ω T ) j  and d j  are highly non-uniform in this case. Actually, (1/ω T ) j  are distributed non-uniformly along the circle ( FIG. 6 ) while d j  are distributed in a sector of unit circle ( FIG. 7 ). This makes the calculation more difficult. For N=10 4  and T=N 8 , it was determined that the optimum number of levels in FMM is 10. With 10 levels in FMM, over 60% of the CPU time was spent on the direct sum in the FMM calculation. Using a single core, it took 3,400s to finish the time dependent part of calculation and about 90% of the CPU time was spent on FMM. For comparison, it took 33,800s to perform the time independent calculation. This shows that the algorithm II is of order O(1) if T&lt;N 2 . 
       FIG. 6  shows the testing of the algorithm IIa, which is suitable for T=N and the algorithm IIb designed for T=N 2 , against the algorithm I. For T&lt;N, the results of the algorithm I, the algorithm IIa and the algorithm IIb are on top of each other. For T&gt;N, the calculation was done for T=N 2 .  FIG. 6 , only shows the results for T&lt;40,000. There is no significant feature in the transient current plot beyond that. 
       FIG. 7  shows the distribution of d j  on the complex plane. 
       FIG. 8  shows the transient current calculated by Algorithm I, Algorithm IIa and Algorithm IIb, IIa and IIb refer to the cases with FMM methods targeting T=N and T=N 2 , respectively. 
     In summary, the exact solution of the algorithm for the transient current always contains time dependent parts. According to the present invention the expression for the current is separated so that, e.g.: for a function f=f(t,x) that depends on time t and space x, it is separated into two part so that f=g(t)h(x). Thus, h(x) can be calculated first, which is a very complicated function involves many multiplications. Eventually, for any time t, the h(x) only needs to be computed once. 
     In addition, the major difference between Algorithm I and II is that for the expression f=g(t)h(x), in algorithm I the multiplication is performed directly; but, for algorithm II, FFT and FMM are adopted to further speed up the multiplication between g(t) and h(x). 
     While the present invention has been particularly shown and described with reference to preferred embodiments thereof; it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.