Computational efficiency analysis of Wu et al.’s fast modular multi-exponentiation algorithm

Very recently, for speeding up the computation of modular multi-exponentiation, Wu et al. presented a fast algorithm combining the complement recoding method and the minimal weight binary signed-digit representation technique. They claimed that the proposed algorithm reduced the number of modular multiplications from 1.503k to 1.306k on average, where the value k is the maximum bit-length of two exponents. However, in this paper, we show that their claim is unwarranted. We analyze the computational efficiency of Wu et al.’s algorithm by modeling it as a Markov chain. Our main result is that Wu et al.’s algorithm requires 1.471k modular multiplications on average.     

Preconditioning the Poincaré-Steklov operator by using Green's function

This paper is concerned with the Poincaré-Steklov operator that is widely used in domain decomposition methods. It is proved that the inverse of the Poincaré-Steklov operator can be expressed explicitly by an integral operator with a kernel being the Green's function restricted to the interface. As an application, for the discrete Poincaré-Steklov operator with respect to either a line (edge) or a star-shaped web associated with a single vertex point, a preconditioner can be constructed by first imbedding the line as the diameter of a disk, or the web as a union of radii of a disk, and then using the Green's function on the disk. The proposed technique can be effectively used in conjunction with various existing domain decomposition techniques, especially with the methods based on vertex spaces (from multi-subdomain decomposition). Some numerical results are reported.

     

Graphs G for which both G and G¯ are Contraction Critically k-Connected

 An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k ^5/3+4k ^3/2. Received: October, 2001 Final version received: September 18, 2002 AMS Classification: 05C40     

An analysis on the efficiency of Euler's method for computing the matrix pth root

It is shown that the matrix sequence generated by Euler's method starting from the identity matrix converges to the principal pth root of a square matrix, if all the eigenvalues of the matrix are in a region including the one for Newton's method given by Guo in 2010. The convergence is cubic if the matrix is invertible. A modification version of Euler's method using the Schur decomposition is developed. Numerical experiments show that the modified algorithm has the overall good numerical behavior.     

Central Schur rings over the projective special linear groups

In [1 Bannai, E. (1991). Subschemes of some association schemes. J. Algebra 14:167–188.[Crossref], [Web of Science ®] , [Google Scholar]], Bannai presents a fusion condition and uses this to consider central Schur rings (S-rings) over the simple groups PSL(2,q) where q is a prime power. In this paper, we concretely describe all such S-rings in terms of symmetric S-rings over cyclic groups. The final section discusses counting these.     

A spectral element method using the modal basis and its application in solving second‐order nonlinear partial differential equations

We present a high‐order spectral element method (SEM) using modal (or hierarchical) basis for modeling of some nonlinear second‐order partial differential equations in two‐dimensional spatial space. The discretization is based on the conforming spectral element technique in space and the semi‐implicit or the explicit finite difference formula in time. Unlike the nodal SEM, which is based on the Lagrange polynomials associated with the Gauss–Lobatto–Legendre or Chebyshev quadrature nodes, the Lobatto polynomials are used in this paper as modal basis. Using modal bases due to their orthogonal properties enables us to exactly obtain the elemental matrices provided that the element‐wise mapping has the constant Jacobian. The difficulty of implementation of modal approximations for nonlinear problems is treated in this paper by expanding the nonlinear terms in the weak form of differential equations in terms of the Lobatto polynomials on each element using the fast Fourier transform (FFT). Utilization of the Fourier interpolation on equidistant points in the FFT algorithm and the enough polynomial order of approximation of the nonlinear terms can lead to minimize the aliasing error. Also, this approach leads to finding numerical solution of a nonlinear differential equation through solving a system of linear algebraic equations. Numerical results for some famous nonlinear equations illustrate efficiency, stability and convergence properties of the approximation scheme, which is exponential in space and up to third‐order in time. Copyright © 2014 John Wiley & Sons, Ltd.     

Prediction error sampling procedure based on dominant Schur decomposition. Application to state estimation in high dimensional oceanic model

Iterative procedure is described to generate patterns of dominant Schur vectors of the system dynamics. Their roles in estimating the filter gain is study. These patterns are produced by several integrations of the model from a set of perturbations. This approach is motivated by a number of interesting results on stability of the filter whose gain is approximated in a subspace of dominant Schur vectors. A simple method for the filter design is presented which is aimed at overcoming the most serious drawback of advanced filtering algorithms for high dimensional systems related to very high computational cost in evaluation of the filter gain.The resulting filter will be compared with the existing ones, showing its relevance from a practical point of view. In order to demonstrate its efficiency, the new filter is tested on various experiments. These experiments include the much studied problem of estimating the solution of the Lorenz system as well as that of assimilating sea surface height observations in a high dimensional oceanic model. It is shown that significant increases in efficiency can be obtained by using this filter and that the proposed filter is very promising for solving realistic assimilation problems in meteorology and oceanography.     

Robust multigrid preconditioners for the high‐contrast biharmonic plate equation

We study the high‐contrast biharmonic plate equation with Hsieh–Clough–Tocher discretization. We construct a preconditioner that is robust with respect to contrast size and mesh size simultaneously based on the preconditioner proposed by Aksoylu et al. (Comput. Vis. Sci. 2008; 11 :319–331). By extending the devised singular perturbation analysis from linear finite element discretization to the above discretization, we prove and numerically demonstrate the robustness of the preconditioner. Therefore, we accomplish a desirable preconditioning design goal by using the same family of preconditioners to solve the elliptic family of PDEs with varying discretizations. We also present a strategy on how to generalize the proposed preconditioner to cover high‐contrast elliptic PDEs of order 2k, k>2. Moreover, we prove a fundamental qualitative property of the solution to the high‐contrast biharmonic plate equation. Namely, the solution over the highly bending island becomes a linear polynomial asymptotically. The effectiveness of our preconditioner is largely due to the integration of this qualitative understanding of the underlying PDE into its construction. Copyright © 2010 John Wiley & Sons, Ltd.