M. Wimmer
Abstract
Computing the Pfaffian of a skew-symmetric matrix is a problem that arises in various fields of physics. Both computing the Pfaffian and a related problem, computing the canonical form of a skew-symmetric matrix under unitary congruence, can be solved easily once the skew-symmetric matrix has been reduced to skew-symmetric tridiagonal form. We develop efficient numerical methods for computing this tridiagonal form based on Gaussian elimination, using a skew-symmetric, blocked form of the Parlett-Reid algorithm, or based on unitary transformations, using block Householder transformations and Givens rotations, that are applicable to dense and banded matrices, respectively. We also give a complete and fully optimized implementation of these algorithms in Fortran (including a C interface), and also provide Python, Matlab and Mathematica implementations for convenience. Finally, we apply these methods to compute the topological charge of a class D nanowire, and show numerically the equivalence of definitions based on the Hamiltonian and the scattering matrix.
Supplemental Material
Available for Download
The proof is given in an electronic appendix, available online in the ACM Digital Library.
Software for Efficient Numerical Computation of the Pfaffian for Dense and Banded Skew-Symmetric Matrices
- Aasen, J. O. 1971. On the reduction of a symmetric matrix to tridiagonal form. BIT Numer. Math. 11, 233--242.Google Scholar
Digital Library
- Akhmerov, A. R., Dahlhaus, J. P., Hassler, F., Wimmer, M., and Beenakker, C. W. J. 2011. Quantized conductance at the Majorana phase transition in a disordered superconducting wire. Phys. Rev. Lett. 106, 5, 057001.Google ScholarCross Ref
- Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., and Sorensen, D. 1999. LAPACK Users’ Guide 3rd Ed. Society for Industrial and Applied Mathematics, Philadelphia, PA. Google ScholarDigital Library
- Bajdich, M. and Mitas, L. 2009. Electronic structure quantum Monte Carlo. Acta Phys. Slov. 59, 81--168.Google Scholar
- Bajdich, M., Mitas, L., Wagner, L. K., and Schmidt, K. E. 2008. Pfaffian pairing and backflow wavefunctions for electronic structure quantum Monte Carlo methods. Phys. Rev. B 77, 115112.Google ScholarCross Ref
- Bardarson, J. H. 2008. A proof of the Kramers degeneracy of transmission eigenvalues from antisymmetry of the scattering matrix. J. Phys. A: Math. Theor. 41, 40, 405203.Google ScholarCross Ref
- Béri, B. 2009. Dephasing-enabled triplet Andreev conductance. Phys. Rev. B 79, 24, 245315.Google ScholarCross Ref
- Bunch, J. R. 1982. A note on the stable decompostion of skew-symmetric matrices. Math. Comput. 38, 475--479.Google Scholar
- Bunch, J. R. and Kaufman, L. 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comput. 31, 137, pp. 163--179.Google ScholarCross Ref
- Evers, F. and Mirlin, A. D. 2008. Anderson transitions. Rev. Mod. Phys. 80, 4, 1355.Google ScholarCross Ref
- Fu, L. and Kane, C. L. 2007. Topological insulators with inversion symmetry. Phys. Rev. B 76, 4, 045302.Google ScholarCross Ref
- Fulga, I. C., Hassler, F., Akhmerov, A. R., and Beenakker, C. W. J. 2011. Scattering formula for the topological quantum number of a disordered multimode wire. Phys. Rev. B 83, 155429.Google ScholarCross Ref
- Galbiati, G. and Maffioli, F. 1994. On the computation of pfaffians. Discrete Appl. Math. 51, 3, 269--275. Google ScholarDigital Library
- Gibbs, N. E., William, G., Poole, J., and Stockmeyer, P. K. 1976. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J. Num. Anal. 13, 2, 236--250.Google ScholarCross Ref
- Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd Ed. The John Hopkins University Press, Baltimore, London. Google ScholarDigital Library
- González-Ballestero, C., Robledo, L., and Bertsch, G. 2011. Numeric and symbolic evaluation of the pfaffian of general skew-symmetric matrices. Comput. Phys. Commun. 182, 10, 2213--2218.Google ScholarCross Ref
- Haake, F. 2004. Quantum Signatures of Chaos. Springer. Google ScholarDigital Library
- Hastings, M. B. and Loring, T. A. 2011. Topological insulators and C*-algebras: Theory and numerical practice. Ann. Physics 326, 7, 1699--1759.Google ScholarCross Ref
- Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia. PA. Google ScholarDigital Library
- Hua, L.-K. 1944. On the theory of automorphic functions of a matrix variable I-geometrical basis. Amer. J. Math. 66, 3, 470--488.Google ScholarCross Ref
- Irony, D. and Toledo, S. 2006. The snap-back pivoting method for symmetric banded indefinite matrices. SIAM. J. Matrix Anal. Appl. 28, 398--424. Google ScholarDigital Library
- Kaufman, L. 1984. Banded eigenvalue solvers on vector machines. ACM Trans. Math. Softw. 10, 73--85. Google ScholarDigital Library
- Kaufman, L. 2000. Band reduction algorithms revisited. ACM Trans. Math. Softw. 26, 551--567. Google ScholarDigital Library
- Kaufman, L. 2007. The retraction algorithm for factoring banded symmetric matrices. Numer. Linear Algebra Appl. 14, 3, 237--254.Google ScholarCross Ref
- Kitaev, A. Y. 2001. Unpaired Majorana fermions in quantum wires. Physics-Uspekhi 44, 10S, 131.Google ScholarCross Ref
- Krauth, W. 2006. Statistical Mechanics: Algorithms and Computations. Oxford University Press, Oxford.Google Scholar
- Lehoucq, R. 1995. The computation of elementary unitary matrices. LAPACK Working Note 72. University of Tennessee.Google Scholar
- Lutchyn, R. M., Sau, J. D., and Das Sarma, S. 2010. Majorana fermions and a topological phase transition in semiconductor-superconductor heterostructures. Phys. Rev. Lett. 105, 7, 077001.Google ScholarCross Ref
- Montvay, I. 1996. An algorithm for gluinos on the lattice. Nucl. Phys. B 466, 1--2, 259--281.Google ScholarCross Ref
- Moore, G. and Read, N. 1991. Nonabelions in the fractional quantum Hall effect. Nucl. Phys. B 360, 2--3, 362--396.Google ScholarCross Ref
- Oreg, Y., Refael, G., and von Oppen, F. 2010. Helical liquids and Majorana bound states in quantum wires. Phys. Rev. Lett. 105, 17, 177002.Google ScholarCross Ref
- Parlett, B. N. and Reid, J. K. 1970. On the solution of a system of linear equations whose matrix is symmetric but not definite. BIT Numer. Math. 10, 386--397.Google Scholar
- Potter, A. C. and Lee, P. A. 2010. Multichannel generalization of Kitaev’s Majorana end states and a practical route to realize them in thin films. Phys. Rev. Lett. 105, 22, 227003.Google ScholarCross Ref
- Rote, G. 2001. Division-Free Algorithms for the Determinant and the Pfaffian: Algebraic and Combinatorial Approaches. In Computational Discrete Mathematics, H. Alt Ed., Springer, 119--135. Google ScholarDigital Library
- Rozložník, M., Shklarski, G., and Toledo, S. 2011. Partitioned triangular tridiagonalization. ACM Trans. Math. Softw. 37, 4, 38:1--38:16. Google ScholarDigital Library
- Rubow, J. and Wolff, U. 2011. A factorization algorithm to compute Pfaffians. Comput. Phys. Comm. 182, 12, 2530--2532.Google ScholarCross Ref
- Schwarz, H. 1968. Tridiagonalization of a symetric band matrix. Numer. Math. 12, 4, 231--241.Google ScholarDigital Library
- Stander, J. W. and Wiegman, N. A. 1960. Canonical forms for certain matrices under unitary congruence. Can. J. Math 12, 438.Google ScholarCross Ref
- Thomas, C. K. and Middleton, A. A. 2009. Exact algorithm for sampling the two-dimensional ising spin glass. Phys. Rev. E 80, 4, 046708.Google ScholarCross Ref
- Ward, R. C. and Gray, L. J. 1978a. Algorithm 530: An algorithm for computing the eigensystem of skew-symmetric matrices and a class of symmetric matrices {F2)}. ACM Trans. Math. Softw. 4, 3, 286--289. Google ScholarDigital Library
- Ward, R. C. and Gray, L. J. 1978b. Eigensystem computation for skew-symmetric and a class of symmetric matrices. ACM Trans. Math. Softw. 4, 3, 278--285. Google ScholarDigital Library
- Wimmer, M., Akhmerov, A. R., Medvedyeva, M. V., Tworzydło, J., and Beenakker, C. W. J. 2010. Majorana bound states without vortices in topological superconductors with electrostatic defects. Phys. Rev. Lett. 105, 4, 046803.Google ScholarCross Ref
- Wimmer, M. and Richter, K. 2009. Optimal block-tridiagonalization of matrices for coherent charge transport. J. Comput. Phys. 228, 8548. Google ScholarDigital Library
Index Terms
- Algorithm 923: Efficient Numerical Computation of the Pfaffian for Dense and Banded Skew-Symmetric Matrices
Recommendations
The generalised Sylvester matrix equations over the generalised bisymmetric and skew-symmetric matrices
A matrix <italic>P</italic> is called a symmetric orthogonal if <italic>P</italic> = <italic>P</italic><italic>T</italic> = <italic>P</italic>−1. A matrix <italic>X</italic> is said to be a generalised bisymmetric with respect to <italic>P</italic> if <...
RGSVD—AN Algorithm for Computing the Kronecker Structure and Reducing Subspaces of Singular $A - \lambda B$ Pencils
An algorithm (RGSVD) for computing the structure elements associated with the Kronecker canonical form (KCF) of a matrix pencil $A - \lambda B$, where A and B are complex m by n matrices, is presented. RGSVD is based on repeated generalized singular ...
A Numerical Method for Computing an SVD-like Decomposition
We present a numerical method for computing the SVD-like decomposition B = QDS -1, where Q is orthogonal, S is symplectic, and D is a permuted diagonal matrix. The method can be applied directly to compute the canonical form of the Hamiltonian matrices ...
Reviews
Charles Raymond Crawford
The Pfaffian of a matrix, like the determinant, is a polynomial in the matrix elements. It is most frequently used in particle physics where the matrix is even-ordered and skew-symmetric, and the determinant is the square of the Pfaffian. In these problems, the Pfaffian is used to define a particular choice of sign for the root of the determinant. The methods in this paper first reduce the given matrix to an equivalent tridiagonal form, from which the Pfaffian can be computed directly. The first section of the paper summarizes several published methods for the reduction of skew-symmetric matrices to tridiagonal form. The second section describes the routines that make up Algorithm 923, and a final section describes the results of tests with those routines. The routines are written in Fortran95, Mathematica, MATLAB, and Python. The Fortran routines are for complex or real matrices in single or double precision. The author also provides C-language interface definitions. The first two sections of the paper include interesting background results on skew-symmetric real and complex matrices, as well as the Pfaffian, supported by an extensive bibliography. The author shows how methods for real skew-symmetric matrices can be adapted for complex matrices. He also describes in detail one application of the Pfaffian to a problem in particle physics. The author mentions three appendices, which are available online. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments