Comments on “Generalised finite Radon transform for N × N images”

In Kingston and Svalbe [1], a generalized finite Radon transform (FRT) that applied to square arrays of arbitrary size N × N was defined and the Fourier slice theorem was established for the FRT. Kingston and Svalbe asserted that “the original definition by Matúš and Flusser was restricted to apply only to square arrays of prime size,” and “Hsung, Lun and Siu developed an FRT that also applied to dyadic square arrays,” and “Kingston further extended this to define an FRT that applies to prime-adic arrays”. It should be said that the presented generalized FRT together with the above FRT definitions repeated the known concept of tensor representation, or tensor transform of images of size N × N which was published earlier by Artyom Grigoryan in 1984-1991 in the USSR. The above mentioned “Fourier slice theorem” repeated the known tensor transform-based algorithm of 2-D DFT [5-11], which was developed for any order N₁ × N₂ of the transformation, including the cases of N × N, when N = 2^r, (r > 1), and N = L^r, (r ≥ 1), where L is an odd prime. The problem of “over-representation” of the two-dimensional discrete Fourier transform in tensor representation was also solved by means of the paired representation in Grigoryan [6-9].     

An agglomerative clustering algorithm using a dynamic k-nearest-neighbor list

In this paper, a new algorithm is developed to reduce the computational complexity of Ward’s method. The proposed approach uses a dynamic k-nearest-neighbor list to avoid the determination of a cluster’s nearest neighbor at some steps of the cluster merge. Double linked algorithm (DLA) can significantly reduce the computing time of the fast pairwise nearest neighbor (FPNN) algorithm by obtaining an approximate solution of hierarchical agglomerative clustering. In this paper, we propose a method to resolve the problem of a non-optimal solution for DLA while keeping the corresponding advantage of low computational complexity. The computational complexity of the proposed method DKNNA + FS (dynamic k-nearest-neighbor algorithm with a fast search) in terms of the number of distance calculations is O(N²), where N is the number of data points. Compared to FPNN with a fast search (FPNN + FS), the proposed method using the same fast search algorithm (DKNNA + FS) can reduce the computing time by a factor of 1.90-2.18 for the data set from a real image. In comparison with FPNN + FS, DKNNA + FS can reduce the computing time by a factor of 1.92-2.02 using the data set generated from three images. Compared to DLA with a fast search (DLA + FS), DKNNA + FS can decrease the average mean square error by 1.26% for the same data set.     

Fast, prime factor, discrete Fourier transform algorithms over GF(2) for 8 ? m ? 10

In this paper it is shown that Winograd’s algorithm for computing convolutions and a fast, prime factor, discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2^m − 1 points over GF(2^m), for 8 ? m ? 10. These new transform techniques can be used to decode Reed-Solomon (RS) codes of block length 2^m − 1. The complexity of this new transform algorithm is reduced substantially from more conventional methods. A computer simulation verifies these new results.     

A (4n − 9)/3 diagnosis algorithm on n-dimensional cube network

As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log₂ N) time, where N = 2ⁿ is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.     

A hybrid polynomial-time algorithm for the dynamic quantity discount lot size model with resale

We propose an efficient optimal algorithm for determining the lot sizes for purchase component in Material Requirement Planning (MRP) environments with deterministic time-phased demand and zero lead time. In this model, backlog is not permitted, the unit purchasing price is based on the all-units discount system with single price break point and resale of the excess units is acceptable at the ordering time. The problem is divided into the sub-plans with specific properties by the dynamic programming (DP) method already presented. By modifying the main structure of the DP method, we present a branch-and-bound algorithm to obtain the optimal ordering policy for each sub-plans. Furthermore, we prove some useful fathoming rules to make the branch-and-bound algorithm very efficient. It has also been shown that the worst-case time complexity function of the presented algorithm is O(N⁴) where N is the number of periods in the planning horizon. Finally, we show the efficiency of the presented algorithm and its fathoming rules by solving some test problems which are randomly generated in various environments.     

Integer programming with 2-variable equations and 1-variable inequalities

We present an efficient algorithm to find an optimal integer solution of a given system of 2-variable equalities and 1-variable inequalities with respect to a given linear objective function. Our algorithm has worst-case running time in O(N²) where N is the number of bits in the input.     

A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems

This paper describes a system-level diagnosis algorithm for hypercube multicomputer systems. The algorithm is based on the PMC model and can isolate all faulty processors to within a set that contains at most one fault-free processor. If we denote by N the total number of processors in a hypercube system to be diagnosed, then, based on the judiciously designed data structures, the algorithm can run in O(Nlog₂N) time; whereas the best-known diagnosis algorithm, the YML algorithm, runs in O(N^2.5) time. Consequently, the new algorithm is remarkably superior to the YML algorithm in terms of the time cost.     

Estimating chlorophyll a concentrations from remote-sensing reflectance in optically shallow waters

A multi-spectral classification and quantification technique is developed for estimating chlorophyll a concentrations, Chl, in shallow oceanic waters where light reflected by the bottom can contribute significantly to the above-water remote-sensing reflectance spectra, R_rs(λ). Classification criteria for determining bottom reflectance contributions for shipboard R_rs(λ) data from the west Florida shelf and Bahamian waters (1998-2001; n = 451) were established using the relationship between R_rs(412)/R_rs(670) and the spectral curvature about 555 nm, [R_rs(412) ? R_rs(670)]/R_rs(555)². Chlorophyll concentrations for data classified as “optically deep” and “optically shallow” were derived separately using best-fit cubic polynomial functions developed from the band-ratios R_rs(490)/R_rs(555) and R_rs(412)/R_rs(670), respectively. Concentrations for transitional data were calculated from weighted averages of the two derived values. The root-mean-square error (RMSE_log10) calculated for the entire data set using the new technique was 14% lower than the lowest error derived using the best individual band-ratio. The standard blue-to-green, band-ratio algorithm yields a 26% higher RMSE_log10 than that calculated using the new method. This study demonstrates the potential of quantifying chlorophyll a concentrations more accurately from multi-spectral satellite ocean color data in oceanic regions containing optically shallow waters.     

In2O3 + xBaO (x = 0.5-5 at.%) - A novel material for trace level detection of NOx in the ambient

Indium oxide (In₂O₃) doped with 0.5-5 at.% of Ba was examined for their response towards trace levels of NO_x in the ambient. Crystallographic phase studies, electrical conductivity and sensor studies for NO_x with cross interference for hydrogen, petroleum gas (PG) and ammonia were carried out. Bulk compositions with x ≤ 1 at.% of Ba exhibited high response towards NO_x with extremely low cross interference for hydrogen, PG and ammonia, offering high selectivity. Thin films of 0.5 at.% Ba doped In₂O₃ were deposited using pulsed laser deposition technique using an excimer laser (KrF) operating at a wavelength of (λ) 248 nm with a fluence of ∼3 J/cm² and pulsed at 10 Hz. Thin film sensors exhibited better response towards 3 ppm NO_x quite reliably and reproducibly and offer the potential to develop NO_x sensors (Threshold limit value of NO₂ and NO is 3 and 25 ppm, respectively).     

Constructing edge-disjoint spanning trees in twisted cubes

The use of edge-disjoint spanning trees or independent spanning trees in a network for data broadcasting has the benefits of increased of bandwidth and fault-tolerance. In this paper, we propose an algorithm which constructs n edge-disjoint spanning trees in the n-dimensional twisted cube, denoted by TQ_n. Because the n-dimensional twisted cube is n-regular, the result is optimal with respect to the number of edge-disjoint spanning trees constructed. Furthermore, we also show that of the n edge-disjoint spanning trees constructed are independent spanning trees. This algorithm runs in time O(N log N) and can be parallelized to run in time O(log N) where N is the number of nodes in TQ_n.     

Monte Carlo TD(λ)-methods for the optimal control of discrete-time Markovian jump linear systems

In this paper, we present an iterative technique based on Monte Carlo simulations for deriving the optimal control of the infinite horizon linear regulator problem of discrete-time Markovian jump linear systems for the case in which the transition probability matrix of the Markov chain is not known. We trace a parallel with the theory of TD(λ) algorithms for Markovian decision processes to develop a TD(λ) like algorithm for the optimal control associated to the maximal solution of a set of coupled algebraic Riccati equations (CARE). It is assumed that either there is a sample of past observations of the Markov chain that can be used for the iterative algorithm, or it can be generated through a computer program. Our proofs rely on the spectral radius of the closed loop operators associated to the mean square stability of the system being less than 1.     

A SimpleO(log N) Time Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

Maximal outerplanar graphs constitute an important class of graphs, often encountered in various applications, e.g., computational geometry, robotics, etc. In this paper, we propose a parallel algorithm for testing the isomorphism of maximal outerplanar graphs. Given the ordered adjacency lists of the two graphs, the proposed algorithm tests their isomorphism inO(log N) time usingNprocessors, for graphs withNnodes on an EREW shared memory model, as well as on a hypercube arhitecture. When the adjacency matrices of the graphs are given, this algorithm can be redesigned onN²processors to run inO(log N) time.     

A fuzzy framework for coordinating pricing and inventory policies for deteriorating items under retailer partial trade credit financing

In this paper, we proposed a generalized economic order quantity (EOQ) – based inventory model using a trade credit policy in a fuzzy sense. The trade credit policy adopted here is a two-level trade credit policy in which the supplier offers the retailer a permissible delay period M, and the retailer, in turn, partially provides customers a permissible delay period N. This study considers fuzzy EOQ model to allow for: (1) selling price dependent demand rate which is imprecise in nature, (2) a profit maximization objective and (3) an imprecise holding cost, ordering cost, purchasing cost, interest earned and interest charged rate. Besides, the cases N ? M and N ? M are explored thoroughly. The objective function for the retailer in fuzzy sense is defuzzified using Modified Graded Mean Integration Representation Method. For the defuzzified objective function sufficient conditions for the existence and uniqueness of the optimal solution are provided. An efficient algorithm is designed to determine the optimal pricing and inventory policies for the retailer. Finally, numerical examples are presented to illustrate the proposed model and the effect of key parameters on optimal solution is examined.     

Strong (n, t, n) verifiable secret sharing scheme

A (t, n) secret sharing divides a secret into n shares in such a way that any t or more than t shares can reconstruct the secret; but fewer than t shares cannot reconstruct the secret. In this paper, we extend the idea of a (t, n) secret sharing scheme and give a formal definition on the (n, t, n) secret sharing scheme based on Pedersen’s (t, n) secret sharing scheme. We will show that the (t, n) verifiable secret sharing (VSS) scheme proposed by Benaloh can only ensure that all shares are t-consistent (i.e. any subset of t shares defines the same secret); but shares may not satisfy the security requirements of a (t, n) secret sharing scheme. Then, we introduce new notions of strong t-consistency and strong VSS. A strong VSS can ensure that (a) all shares are t-consistent, and (b) all shares satisfy the security requirements of a secret sharing scheme. We propose a strong (n, t, n) VSS based on Benaloh’s VSS. We also prove that our proposed (n, t, n) VSS satisfies the definition of a strong VSS.     

An efficient parity detection technique using the two-moduli set {2 − 1, 2 + 1}

Lu and Chiang used both the table lookup and fractional number approaches to discover the parity of an RNS number. To eliminate the need for table space and time for computing fractions, a two-moduli set {2^h − 1, 2^h + 1} is used to speed up the technique proposed by Lu and Chiang. Based on this modified two-moduli set, it is found that the parity of an RNS number X = (x₁, x₂) is if x₁ ? x₂. On the contrary, if x₁ < x₂, the parity of X is .     

Second order (F, α, ρ, d)-convexity and duality in multiobjective programming

A class of second order (F, α, ρ, d)-convex functions and their generalizations is introduced. Using the assumptions on the functions involved, weak, strong and strict converse duality theorems are established for a second order Mond-Weir type multiobjective dual.     

On the K best integer network flows

We address the problem of finding the K best integer solutions of a linear integer network flow problem. We design an O(f(n,m,L,U)+KmS(n,m,L)) time and O(K+m) memory space algorithm to determine the K best integer solutions, in a directed network with n nodes, m arcs, maximum absolute value cost L, and an upper bound U on arc capacities and node supplies. f(n,m,L,U) is the best time needed to solve the minimum cost flow problem in a directed network and S(n,m,L) is the best time to solve the single-source shortest path problem in a network with non-negative lengths. The introduced algorithm efficiently determines a “proper minimal cycle” by taking advantage of the relationship between the best solutions. This way, we improve the theoretical as well as practical memory space bounds of the well-known method due to Hamacher. Our computational experiments confirm this result.     

Mathematical models for preemptive shop scheduling problems

More than half a century has passed since Bowman and Dantzig (1959) [13] and [14] introduced their models for preemptive shop scheduling problems. A more efficient model seems to be needed to address all the aspects involved in the problem. We introduce a new Integer Linear Programming (ILP) formulation as a new method for solving the preemptive Job Shop Scheduling Problem (pJSSP). The dimension of the new model, unlike those of the existing ones, depends solely on the number of jobs and machines irrespective of processing times. The proposed model is used as an optimal, two-phase approach. In phase one, the model is solved to obtain the start and completion times of each operation on each machine. In phase two, a simple algorithm in O(mn log n) steps is used to turn these times into a complete and optimal schedule. Different preemptive flow shop problems are studied as special cases of the pJSSP while some related properties are also discussed. Finally, the higher efficiency of the proposed model is verified both theoretically and computationally through its comparison with conventional methods commonly in use.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

Efficient uncertainty quantification with the polynomial chaos method for stiff systems

The polynomial chaos (PC) method has been widely adopted as a computationally feasible approach for uncertainty quantification (UQ). Most studies to date have focused on non-stiff systems. When stiff systems are considered, implicit numerical integration requires the solution of a non-linear system of equations at every time step. Using the Galerkin approach the size of the system state increases from n to S × n, where S is the number of PC basis functions. Solving such systems with full linear algebra causes the computational cost to increase from O(n³) to O(S³n³). The S³-fold increase can make the computation prohibitive. This paper explores computationally efficient UQ techniques for stiff systems using the PC Galerkin, collocation, and collocation least-squares (LS) formulations. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the Jacobian matrix to reduce the computational cost. The numerical results show a run time reduction with no negative impact on accuracy. In the stochastic collocation formulation, we propose a least-squares approach based on collocation at a low-discrepancy set of points. Numerical experiments illustrate that the collocation least-squares approach for UQ has similar accuracy with the Galerkin approach, is more efficient, and does not require any modification of the original code.