Our discussion of Markov chains, with the exception of mentioning the Metropolis and heat-bath algorithms, has so far been very general with little contact with issues and opportunities related to specific applications. In this chapter, we recall that our target is many-body problems defined on a lattice and introduce several frameworks exploiting what is special about Markov processes for these types of problems. We consider here classical many-body problems, using the Ising model as the representative. Our discussion will be extended to various quantum many-body problems and algorithms in subsequent chapters.

Many-body phase space

The numerical difficulty of studying many-body problems on a lattice arises from the fact that their phase space Ω is a direct product of many phase spaces of local degrees of freedom. Generally, a local phase space is associated with each lattice site. If n is the size of this phase space and N is the number of lattice sites, then the number of states |Ω| available to the whole system is nN. In other words, the number of states in the phase space grows exponentially fast with the physical size of the system. For example, in the Ising model, the Ising spin si on each site can take one of the two values ±1, and hence the number of states in the total phase space is 2N.

In Chapter 1, we noted that this exponential scaling thwarts deterministic solutions and is a reason why we use the Monte Carlo method. The exponentially large number of states implies that the enumeration of all states, which requires a computational effort proportional to the size of the phase space, is not an option for a problem with a large number of sites. As discussed in Section 2.7, the Monte Carlo method generally samples from a compressed phase space, avoiding the need to solve the entire problem. However, even with this advantage, can we reduce the computational effort to a manageable level?

An obvious requirement is that we can equilibrate the simulation in a reasonable amount of computer time. We know that the Markov process converges to a stationary state sampling some distribution (Section 2.4), and for detailed balance algorithms, Rosenbluth's theorem (Section 2.6) guarantees monotonic convergence.

Recent trends in computer hardware have made modern computers parallel computers; that is, the power of today's computers depends on the number of processors. In order to use these powerful machines, we must split the algorithmic tasks into pieces and assign them to a large number of processors. In many cases, this requires nontrivial modifications of the algorithm. In this chapter, we discuss several basic concepts about parallelizing an algorithm and illustrate them in the context of loop/cluster identification.

Parallel architectures

The key issue in parallel computation is the distribution of computer memory. In other words, how much memory is available and at what access speed. Memories are organized in a hierarchical structure: L1 cache, L2 cache, main memory, and so on, all with different access speeds. The access speed also depends on the physical distance between the computing unit and the memory block.

Discussing how to fine-tune computer programs, taking all machine details into account, is clearly beyond the scope of this book. Therefore, in the following, we focus our discussion of parallel computers on two common types of architectures (Fig. 13.1): shared memory and distributed memory. In either case, we assume that the parallel computer has Np processors.

In most parallel computers available today, each local memory block is directly accessible by only a small number of processors in the local processor block which is physically closest to it. To access a remote block of memory, a processor must communicate with another processor that has direct access to this block. In some sense, the shared-memory architecture is a model for a local processor block. Alternatively, it can be regarded as a model of the whole computer system in which the communication cost is negligible. In this model, we do not have to account for the process of communicating between the processors. We simply assume that they are all reading and writing to the same block of memory, and each processor immediately knows when something is written to memory by another. The distributed-memory architecture, on the other hand, is a model in which every processor monopolizes the access to the block of memory that it possesses, and for a processor to get the information written on another processor's memory, the owner of the information must explicitly send it the content of this memory.

This chapter introduces a finite-temperature algorithm for the simulation of interacting electrons on a lattice. Because this algorithm was developed by Blankenbecler, Scalapino, and Sugar (1981; Scalapino and Sugar, 1981), it is sometimes called the BSS algorithm. The method uses a Hubbard-Stratonovich transformation to convert the interacting electron problem into a noninteracting one coupled to an imaginarytime- dependent auxiliary field. For this reason, it is also called the auxiliary-field method. We use here yet another name, the determinant method, which is fitting because the transformation to a problem of noninteracting electrons generates determinants as the statistical weights. The finite-temperature determinant algorithm is a general-purpose electron algorithm that enables computations of a wide variety of local observables and correlation functions. For a discussion of a zero-temperature determinant method, refer to Appendix I.

Theoretical framework

Feynman and Hibbs (1965) formulated quantum mechanics in terms of integrals over all paths in configuration space. In real time, each path contributes a phase to the integral that is determined by the classical action along the path. Two paths can interfere constructively or destructively. In the classical limit, only the stationary-phase path is important. Being characterized by many interfering paths, real-time quantum dynamics more than challenges importance sampling. Statistical mechanics, on the other hand, involves path integrals in imaginary time. Contributions to the integrals vary exponentially in magnitude but not in phase. Thus, the path integral is dominated by paths of large magnitude. The tasks of a quantum Monte Carlo method are identifying these important paths and sampling them efficiently.

In this chapter, we address the classicization of many-electron problems at finite temperatures via a Feynman path integral. The result is a method often called the determinant method as the weights of the paths can be expressed as determinants, hardly classical-looking weights, but ones quite suggestive of the antisymmetry of Fermion states. Sampling these weights efficiently and in a stable manner requires special techniques. We begin with a brief overview to motivate the general form of the classical representation and the weights we need to sample.

This chapter, like the previous one, describes quantum Monte Carlo methods for the simulation of a system of interacting electrons at nonzero temperature. Here, we target a particular class of problems, characterized by a small number of correlated sites or orbitals, that we call impurity problems. While we could apply the methods of the previous chapter to such impurity models, the algorithms discussed here are more advantageous not only because they work in continuous imaginary time and hence lack the Trotter approximation error inherent to the previous methods, but also because they manipulate determinants of matrices of smaller size, which can be handled more efficiently. At the same time, the continuous-time approach is applicable to broader classes of impurity problems.

Driving the development of these continuous-time impurity solvers was the desire to perform more efficient simulations of correlated lattice models within the framework of dynamical mean-field theory. This formalism maps the lattice problem onto an impurity problem, whose parameters are determined by a self-consistency condition. In some cases, the self-consistent solution gives a good approximation of the properties of the original lattice problem. When we combine this dynamical mean-field approximation with the local-density approximation for electronic structure calculations, we obtain a powerful scheme for electronic structure calculations of strongly correlated materials. In this chapter we discuss the most important classes of impurity models, sketch the basics of the dynamical mean-field approximation, and detail the different variants of continuous-time impurity solvers.

Quantum impurity models

A quantum impurity model describes an atom or molecule embedded in some host with which it exchanges electrons, spin, and energy. This exchange allows the impurity to make transitions between different quantum states, and in the presence of interactions within or between the impurity orbitals, these transitions lead to nontrivial dynamical properties. Quantum impurity models play a prominent role, for example, in the theoretical description of the magnetic and electric properties of dilute metal alloys and in theoretical studies of quantum dots and molecular conductors. These models also appear as an auxiliary problem whose solution yields the dynamical mean-field description of correlated lattice models.

Quantum Monte Carlo versions of the power method for finding ground states come with different names, including the projector method, diffusion Monte Carlo, and Green's function Monte Carlo. These quantum Monte Carlo methods are primarily adoptions of methods developed for classical problems. We summarize the basics of deterministic power methods, detail key features of Monte Carlo power methods, and put these concepts into the context of quantum ground state calculations. We conclude the chapter by outlining power methods that allow the computation of a few excited states. In the computation of excited states, we encounter sign problems, which are discussed inmore detail in Chapter 11. Themethods and techniques of the present chapter are very general and most usefully applied to systems of Bosons and to systems of Fermions and quantum spins that do not suffer from a sign problem.

Deterministic direct and inverse power methods

The power method is over a century old. As a deterministic method, it originally was combined with the deflation technique (Meyer, 2000; Stewart, 2001b) as a method to compute all the eigenvalues and eigenvectors of small matrices. Today, its deterministic use is limited primarily to special applications involving very large, sparse matrices. Many of these applications are in the study of quantum lattice models as the corresponding Hamiltonian matrices are typically very sparse. In these applications, we can perhaps initially store in computer memory the relatively small number of nonzero matrix elements and all the vectors. Soon, because of what is undoubtedly the now familiar exponentially increasing number of basis states that determines the order of the Hamiltonian matrix and hence the size of our vectors, we reach the point where computer memory restrictions allow us to store only a few vectors and we need to compute the matrix elements on the fly. When we have problems for which we cannot even store all the components of one vector, the power method's expression as a Monte Carlo procedure is our only option. With it, we can compute a few of the extremal eigenvalues, that is, a few of the largest or smallest eigenvalues.

The mathematical basis for the method is simple.