ABSTRACT Approximate block diagonalization is a problem of transforming a given symmetric matrix as close to block diagonal as possible by symmetric permutations of its rows and columns. This problem arises as a preprocessing stage of various scientific calculations and has been shown to be NP‐complete. In this paper, we consider solving this problem approximately using the D‐Wave Advantage quantum annealer. For this purpose, several steps are needed. First, we have to reformulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. Second, the QUBO has to be embedded into the physical qubit network of the quantum annealer. Third, and optionally, reverse annealing for improving the solution can be applied. We propose two QUBO formulations and four embedding strategies for the problem and discuss their advantages and disadvantages. Through numerical experiments, it is shown that the combination of domain‐wall encoding and D‐Wave's automatic embedding is the most efficient in terms of usage of physical qubits, while the combination of one‐hot encoding and automatic embedding is superior in terms of the probability of obtaining a feasible solution. It is also shown that reverse annealing is effective in improving the solution for medium‐sized problems.

We consider the problem of transforming a given symmetric matrix into a nearly block diagonal form by permutation of its rows and columns. Such a transformation is useful as preconditioning to accelerate the convergence of an eigenvalue solver, but the problem of finding an optimal permutation that maximizes the Frobenius norms of the diagonal blocks is NP-complete. We formulate this problem as QUBO (Quadratic Unconstrained Binary Optimization) and solve it using D-Wave Advantage quantum annealing machine. Experimental results on small problems show that the true minimum can be obtained with high probability. We also discuss how to improve the mapping of the problem onto the physical qubit network to increase the size of the problems that can be solved.

We consider computing the QR factorization with column pivoting (QRCP) for a tall and skinny matrix, which has important applications including low-rank approximation and rank determination. Motivated by recent progresses of Cholesky QR type algorithms for tall-skinny QR factorization (without pivoting), we propose a new Cholesky QR type algorithm for tall-skinny QRCP, which we call Iterative Cholesky QR with Column Pivoting (Ite-CholQR-CP). Through performance evaluation, it is confirmed that Ite-CholQR-CP provides a solution as accurate as that by Householder QR with column pivoting (HQR-CP), which is a widely-used conventional algorithm. In addition, Ite-CholQR-CP outperforms HQR-CP in execution time in single node and distributed parallel computations: up to 45x (single node computation) and 27x (distributed parallel computation) speedup.

Summary We consider automatic performance tuning of dense symmetric eigenvalue problems using ATMathCoreLib, which is a library to assist automatic tuning. We deal with two problems, namely, automatic code selection for the symmetric generalized eigenvalue problem in distributed‐memory parallel environments and automatic parameter tuning in tridiagonalization of dense symmetric matrices on multicore processors. As for the first problem, numerical experiments show that ATMathCoreLib can choose the fastest solver for a given computing environment and problem size quickly even if the fluctuation in the execution time is as high as 40%. As for the second problem, ATMathCoreLib was able to select nearly optimal combinations of the algorithm and its parameter reliably and efficiently for various computing environments and matrix sizes. The performance of auto‐tuning was further enhanced by incorporating a user‐provided execution‐time model into ATMathCoreLib.

Summary The one‐sided block Jacobi (OSBJ) method is known to be an efficient method for computing the singular value decomposition on a parallel computer. In this paper, we focus on the most recent variant of the OSBJ method, the one with parallel dynamic ordering and variable blocking, and present both theoretical and experimental analyses of the algorithm. In the first part of the paper, we provide a detailed theoretical analysis of its convergence properties. In the second part, based on preliminary performance measurement on the Fujitsu FX10 and SGI Altix ICE parallel computers, we identify two performance bottlenecks of the algorithm and propose new implementations to resolve the problem. Experimental results show that they are effective and can achieve up to 1.8 and 1.4 times speedup of the total execution time on the FX10 and the Altix ICE, respectively. Comparison with the ScaLAPACK SVD routine PDGESVD shows that our OSBJ solver is efficient when solving small to medium sized problems (n < 10000) using modest number ( < 100) of computing nodes. Copyright © 2016 John Wiley & Sons, Ltd.

The nonlinear eigenvalue problem plays an important role in various fields such as nonlinear elasticity, electronic structure calculation and theoretical fluid dynamics. We recently proposed a new algorithm for the nonlinear eigenvalue problem, which reduces the original problem to a smaller generalized linear eigenvalue problem with Hankel coefficient matrices through complex contour integral. This algorithm has a unique feature that it can find all the eigenvalues in a closed curve on the complex plane. Moreover, it has large-grain parallelism and is suited for execution in a Grid environment. In this paper, we study the numerical properties of our algorithm theoretically. In particular, we analyze the effect of numerical integration to the computed eigenvalues and give a guideline on how to choose the size of the Hankel matrices properly. Also, we show the parallel performance of our algorithm implemented on a PC cluster using OmniRPC, a Grid RPC system. Parallel efficiency of 75% is achieved when solving a nonlinear eigenvalue problem of order 1000 using 14 processors.

In this paper, we present a new approach to optimizing the blocking strategy for the householder QR decomposition. In high performance implementations of the householder QR algorithm, it is common to use a blocking technique for the efficient use of the cache memory. There are several well known blocking strategies like the fixed-size blocking and recursive blocking, and usually their parameters such as the block size and the recursion level are tuned according to the target machine and the problem size. However, strategies generated with this kind of parameter optimization constitute only a small fraction of all possible blocking strategies. Given the complex performance characteristics of modern microprocessors, non-standard strategies may prove effective on some machines. Considering this situation, we first propose a new universal model that can express a far larger class of blocking strategies than has been considered so far. Next, we give an algorithm to find a near-optimal strategy from this class using dynamic programming. As a result of this approach, we found an effective blocking strategy that has never been reported. Performance evaluation on the Opteron and Core2 processors show that our strategy achieves about 1.2 times speedup over recursive blocking when computing the QR decomposition of a 6000 times 6000 matrix.

CDD weather derivatives are widely used to hedge weather risks and their fast and accurate pricing is an important problem in financial engineering. In this paper, we propose an efficient parallelization strategy of a pricing algorithm for the CDD derivatives. The algorithm uses the fast Gauss transform to compute the expected payoff of the derivative and has proved faster and more accurate than the conventional Monte Carlo method. However, speeding up the algorithm on a distributed-memory parallel computer is not straightforward because naive parallelization will require a large amount of inter-processor communication. Our new parallelization strategy exploits the structure of the fast Gauss transform and thereby reduces the amount of inter-processor communication considerably. Numerical experiments show that our strategy achieves up to 50% performance improvement over the naive one on a 16-node Mac G5 cluster and can compute the price of a representative CDD derivative in 7 seconds. This speed is adequate for almost any applications.