An LDLT factorization based ADI algorithm for solving large-scale differential matrix equations

Large-scale differential matrix equations appear in many applications like optimal control of partial differential equations, balanced truncation model order reduction of linear time varying systems etc. Here, we will focus on matrix Riccati differential equations (RDE). Solving such matrix valued ordinary differential equations (ODE) is a highly storage and time consuming process. Therefore, it is necessary to develop efficient solution strategies minimizing both. We present an LDL^T factorization based ADI method for solving algebraic Lyapunov equations (ALE) arising in the innermost iteration during the application of Rosenbrock ODE solvers to RDEs. We show that the LDL^T-type decomposition avoids complex arithmetic, as well as cancellation effects arising from indefinite right hand sides of the ALEs appearing in the classic ZZ^T based approach. Additionally, a certain number of linear system solves can be saved within the ADI algorithm by reducing the number of column blocks in the right hand sides while the full accuracy of the standard low-rank ADI is preserved. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A fast algorithm for evaluating nth order tri-diagonal determinants

The cost of all existing algorithms for evaluating the nth order determinants (Numerical Analysis, 7th Edition, Brooks & Cole Publishing, Pacific Grove, CA, 2001) is at most O(n³). In the current article we present a new efficient computational algorithm for evaluating the nth order tri-diagonal determinants with cost O(n) only. The algorithm is suited for implementation using Computer Algebra Systems such as MAPLE and MACSYMA. Some examples are given to illustrate the algorithm.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.     

An exponential high‐order compact ADI method for 3D unsteady convection–diffusion problems

In this article, we develop an exponential high order compact alternating direction implicit (EHOC ADI) method for solving three dimensional (3D) unsteady convection–diffusion equations. The method, which requires only a regular seven‐point 3D stencil similar to that in the standard second‐order methods, is second order accurate in time and fourth‐order accurate in space and unconditionally stable. The resulting EHOC ADI scheme in each alternating direction implicit (ADI) solution step corresponding to a strictly diagonally dominant matrix equation can be solved by the application of the one‐dimensional tridiagonal Thomas algorithm with a considerable saving in computing time. Numerical experiments for three test problems are carried out to demonstrate the performance of the present method and to compare it with the classical Douglas–Gunn ADI method and the Karaa's high‐order compact ADI method. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

A fourth-order compact ADI method for solving two-dimensional unsteady convection–diffusion problems

In this article, an exponential high-order compact (EHOC) alternating direction implicit (ADI) method, in which the Crank–Nicolson scheme is used for the time discretization and an exponential fourth-order compact difference formula for the steady-state 1D convection–diffusion problem is used for the spatial discretization, is presented for the solution of the unsteady 2D convection–diffusion problems. The method is temporally second-order accurate and spatially fourth order accurate, which requires only a regular five-point 2D stencil similar to that in the standard second-order methods. The resulting EHOC ADI scheme in each ADI solution step corresponds to a strictly diagonally dominant tridiagonal matrix equation which can be inverted by simple tridiagonal Gaussian decomposition and may also be solved by application of the one-dimensional tridiagonal Thomas algorithm with a considerable saving in computing time. The unconditionally stable character of the method was verified by means of the discrete Fourier (or von Neumann) analysis. Numerical examples are given to demonstrate the performance of the method proposed and to compare mostly it with the high order ADI method of Karaa and Zhang and the spatial third-order compact scheme of Note and Tan.     

Two-time level ADI finite volume method for a class of second-order hyperbolic problems

In this paper, we develop a two-time level alternating direction implicit (ADI) method for a class of second-order hyperbolic problems on a rectangular domain. The method builds on the finite volume method with biquadratic basis functions for the discretization in space, and a Crank-Nicolson approach for the time stepping. We obtain a second-order error estimation in the H¹ norm. Numerical experiments are performed to demonstrate the theoretical findings.     

ADI quadratic finite volume element methods for second order hyperbolic problems

We use the biquadratic elements to develop an alternating direction implicit (ADI) finite volume element method for second order hyperbolic problems in two spatial dimensions. The optimal H ¹-norm error estimate of second order accuracy is proved. Numerical experiments that corroborate the theoretical analysis are also presented.     

Determining dimension of the solution component that contains a computed zero of a polynomial system

When the Jacobian of a computed numerical solution of a polynomial system in Cn allows very small singular values, the solution could be isolated with a multiple multiplicity or may belong to a solution component with positive dimension. The algorithm constructed in this article intends to differentiate those cases by determining the dimension of the solution component M in which the solution lies. Of particular interest is the case when dim(M)=0, then the solution is of course isolated. While the proposed algorithm is experimental, it has been tested successfully on the class of problems with the solution in question belonging to a reduced component. Numerical results are provided to illustrate the accuracy of the algorithm.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Read-Once Functions Revisited and the Readability Number of a Boolean Function

In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrance graph is P₄-free.We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2^k function and a read 2^k formula for F for f can be obtained in polynomial time.     

Exact algorithms for dominating set

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969ⁿ) time and polynomial space algorithm.     

An unconditionally stable spatial sixth-order CCD-ADI method for the two-dimensional linear telegraph equation

The telegraph equation is one of the important models in many physics and engineering. In this work, we discuss the high-order compact finite difference method for solving the two-dimensional second-order linear hyperbolic equation. By using a combined compact finite difference method for the spatial discretization, a high-order alternating direction implicit method (ADI) is proposed. The method is O(τ² + h⁶) accurate, where τ, h are the temporal step size and spatial size, respectively. Von Neumann linear stability analysis shows that the method is unconditionally stable. Finally, numerical examples are used to illustrate the high accuracy of the new difference scheme.     

A new fourth‐order numerical algorithm for a class of three‐dimensional nonlinear evolution equations

In this article, a new compact alternating direction implicit finite difference scheme is derived for solving a class of 3‐D nonlinear evolution equations. By the discrete energy method, it is shown that the new difference scheme has good stability and can attain second‐order accuracy in time and fourth‐order accuracy in space with respect to the discrete H¹ ‐norm. A Richardson extrapolation algorithm is applied to achieve fourth‐order accuracy in temporal dimension. Numerical experiments illustrate the accuracy and efficiency of the extrapolation algorithm. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Scheduling linear deteriorating jobs to minimize the number of tardy jobs

In this paper a problem of scheduling a single machine under linear deterioration which aims at minimizing the number of tardy jobs is considered. According to our assumption, processing time of each job is dependent on its starting time based on a linear function where all the jobs have the same deterioration rate. It is proved that the problem is NP-hard; hence a branch and bound procedure and a heuristic algorithm with O(n ²) is proposed where the heuristic one is utilized for obtaining the upper bound of the B&B procedure. Computational results for 1,800 sample problems demonstrate that the B&B method can solve problems with 28 jobs quickly and in some other groups larger problems are also solved. Generally, B&B method can optimally solve 85% of the samples which shows high performance of the proposed method. Also it is shown that the average value of the ratio of optimal solution to the heuristic algorithm result with the objective ??(1 ? Ui) is at most 1.11 which is more efficient in comparison to other proposed algorithms in related studies in the literature.     

ADI preconditioned Krylov methods for large Lyapunov matrix equations

In the present paper, we propose preconditioned Krylov methods for solving large Lyapunov matrix equations AX+XA^T+BB^T=0. Such problems appear in control theory, model reduction, circuit simulation and others. Using the Alternating Direction Implicit (ADI) iteration method, we transform the original Lyapunov equation to an equivalent symmetric Stein equation depending on some ADI parameters. We then define the Smith and the low rank ADI preconditioners. To solve the obtained Stein matrix equation, we apply the global Arnoldi method and get low rank approximate solutions. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approaches.     

A fast boundary element algorithm for time-dependant potential problems

The numerical solution of time-dependant potential problems via the boundary element has been crippled by the high computational cost due to the inherent time history constraint in the integral representation. Using a boundary-only formulation, the time integrations, at any instant in time, have to be evaluated starting from the initial time. This time-history dependence becomes impractical and inadequate for problems where computations are to be performed for extended times. This also made the boundary element uncompetitive compared to the domain-mesh based methods, such as finite difference and finite element methods, for the solution of transient potential problems. Generally, the evaluation of the potential at N domain points using M boundary points at the Kth time step requires an amount of computer operations of the order O(KM²+KNM). This paper presents an algorithm which requires a computational cost of the order of only O(M²+NM), where the dependence from the past K-steps is removed. The algorithm combines the boundary element method and a scheme, which uses virtual collocation points and radial basis functions to approximate the domain integral.     

Fast Fourier-Galerkin methods for solving singular boundary integral equations: Numerical integration and precondition

We develop a fast fully discrete Fourier-Galerkin method for solving a class of singular boundary integral equations. We prove that the number of multiplications used in generating the compressed matrix is O(nlog³n), and the solution of the proposed method preserves the optimal convergence order O(n^−t), where n is the order of the Fourier basis functions used in the method and t denotes the degree of regularity of the exact solution. Moreover, we propose a preconditioning which ensures the numerical stability when solving the preconditioned linear system. Numerical examples are presented to confirm the theoretical estimates and to demonstrate the approximation accuracy and computational efficiency of the proposed algorithm.     

Analysis of alternating direction collocation methods for parabolic and hyperbolic problems in two space variables

While alternating direction implicit (ADI) collocation methods have been used for several years to solve parabolic problems in several space variables, no convergence analysis has been derived for any of these methods. We formulate and rigorously analyze ADI collocation schemes applied to the inhomogeneous heat and wave equations on the unit square subject to homogeneous Dirichlet boundary conditions and appropriate initial conditions. We prove that each method is second-order accurate in time and of optimal accuracy in space in the L² and H₀¹ norms. Numerical experiments confirm the predicted rates of convergence. © 1993 John Wiley & Sons, Inc.     

A method to accelerate the rate of convergence of a class of optimization algorithms

Supposez ∈ E ⁿ is a solution to the optimization problem minimizeF(x) s.t.x ∈ E ⁿ and an algorithm is available which iteratively constructs a sequence of search directions {s _j } and points {x _j } with the property thatx _j →z. A method is presented to accelerate the rate of convergence of {x _j } toz provided that n consecutive search directions are linearly independent. The accelerating method uses n iterations of the underlying optimization algorithm. This is followed by a special step and then another n iterations of the underlying algorithm followed by a second special step. This pattern is then repeated. It is shown that a superlinear rate of convergence applies to the points determined by the special step. The special step which uses only first derivative information consists of the computation of a search direction and a step size. After a certain number of iterations a step size of one will always be used. The acceleration method is applied to the projection method of conjugate directions and the resulting algorithm is shown to have an (n + 1)-step cubic rate of convergence. The acceleration method is based on the work of Best and Ritter [2].