Broadcast-efficient protocols for mobile radio networks

The main contribution of this work is to present elegant broadcast-efficient protocols for permutation routing, ranking, and sorting on single-hop Mobile Radio Networks with p stations and k radio channels, denoted by MRN(p,k). Clearly, any protocol performing these tasks on n items must perform ⁿ/_k broadcast rounds because each item must be broadcast at least once. We begin by presenting an optimal off-line permutation routing protocol using ⁿ /_k broadcast rounds for arbitrary k, p, and n. Further, we show that optimal on-line routing can be performed in ⁿ/ _k broadcast rounds, provided that either k=1 or p=n. We then go on to develop an online routing protocol that takes 2ⁿ/ _k+k-1 broadcast rounds on the MRN(p,k), whenever k⩽√^p/₂. Using these routing protocols as basic building blocks, we develop a ranking protocol that takes 2ⁿ /_k+o(ⁿ/_k) broadcast rounds as well as a sorting protocol that takes 3ⁿ/_k+o(ⁿ/_k) broadcast rounds, provided that k ϵ o(√n) and p=n. Finally, we develop a ranking protocol that takes 3ⁿ/_k+o(ⁿ/ _k) broadcast rounds, as well as a sorting protocol that takes 4ⁿ/_k+o(ⁿ/_k) broadcast rounds on the MRN(p,k), provided that k⩽√^p/₂ and p ϵ o(n). Featuring very low proportionality constants, our protocols offer a vast improvement over the state of the art     

Square meshes are not optimal for convex hull computation

Recently it has been noticed that for semigroup computations and for selection, rectangular meshes with multiple broadcasting yield faster algorithms than their square counterparts. The contribution of the paper is to provide yet another example of a fundamental problem for which this phenomenon occurs. Specifically, we show that the problem of computing the convex hull of a set of n sorted points in the plane can be solved in O(n^1/8 log ^3/4) time on a rectangular mesh with multiple broadcasting of size n^3/8 log^1/4 n×n^5/8/log^1/4n. The fastest previously known algorithms on a square mesh of size √n×√n run in O(n^1/6) time in case the n points are pixels in a binary image, and in O(n^1/6log^3/2 n) time for sorted points in the plane     

Minimizing the distance to one evader while chasing another

To approach a simple game Δ² of P and E = {E₁, E₂} with no a priori evaders' role assignment and the payoff equal to the distance to one evader at an instant of catching another, we introduce a concept of casting and study the games Δ_1,2 and Δ_2,1 for preassigned and Δ_p² for open-loop casting procedures. Since Δ_p² is reduced to Δ_1,2 or Δ_2,1 which, in turn, are distinguished only by their notations, we focus attention mainly on Δ_1,2. According to the tenet of transition, Δ_1,2 is divided into a concatenation of Δ_1,2^b (basic) and Δ_1,2^a (auxiliary) games that model the problem before and after the first instant of E₁ capture. The games Δ_1,2^a, Δ_1,2^b, Δ_1,2 are studied one after another with use of the Isaacs' approach extended by Berkowitz, Breakwell, Bernhard et al.     

An O((log log n)2) time algorithm to compute the convexhull of sorted points on reconfigurable meshes

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size √n×√n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)²) time on a reconfigurable mesh of size √n×√n. With slight modifications, this algorithm can be implemented to run in O((log log n)²) time on a reconfigurable mesh of size √n/loglogn×√n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take Ω(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes     

Analysis of Parallel Algorithms for Matrix Chain Product and Matrix Powers on Distributed Memory Systems

Given N matrices A₁, A_2,...,A_N of size NtimesN, the matrix chain product problem is to compute A₁timesA₂times...timesA_N. Given an NtimesN matrix A, the matrix powers problem is to calculate the first N powers of A, that is, A, A², A³,..., A^N. We solve the two problems on distributed memory systems (DMSs) with p processors that can support one-to-one communications in T(p) time. Assume that the fastest sequential matrix multiplication algorithm has time complexity O(N^alpha), where the currently best value of a is less than 2.3755. Let p be arbitrarily chosen in the range 1lesplesN^alpha+1/(log N)². We show that the two problems can be solved by a DMS with p processors in T_chain(N,p)=O((N^alpha+1/p)+T(p))((N^2(2+1/alpha/p^2/alpha)(log+p/N)^1-2/alpha+log+((p log N)/N^alpha)) and T_power (N,p)=O(N^alpha+1/p+T(p)((N^2(1+1/alpha)/p^2/alpha)(log+p/2 log N)^1-2/alpha+(log N)²))) times, respectively, where the function log+ is defined as follows: log+ x=log x if xges1 and log+ x=1 if 0相似文献   

Quartic discriminants and tensor invariants

Discusses the calculation of discriminants of polynomials. The discriminant is a function of the coefficients that indicates if the polynomial has any double roots. The discriminant Δ₄ of a homogeneous quartic f(x,w) = Ax⁴+4Bx³w+6Cx² w²+4Dxw³+Ew⁴ = 0 is Δ₄ = 27(I₃)²-(I₂)³, where I₂ = AE-4BD+3C² and I₃ = ACE-AD ²-B²E+2BCD-C³ (this is the Hilbert representation). The author shows how to write the discriminant as a tensor diagram. The discriminant of a polynomial is an example of an invariant quantity. Tensor diagrams are particularly useful to express invariant quantities. Adding a dimension moves us from the world of (1D) homogeneous polynomials to 2D homogeneous (2DH) geometry (curves in the projective plane). It is shown that a relationship exists between the possible root structures of a 4th-order polynomial and the possible degeneracies of a 3rd-order curve     

Production of singlet oxygen by Ru(dpp(SO3)2)3 incorporated in polyacrylamide PEBBLES

Polyacrylamide (PAA) and amine-functionalized PAA (AFPAA) nanoparticles with disulfonated 4,7-diphenyl-1,10-phenantroline ruthenium (Ru(dpp(SO₃)₂)₃) have been prepared. The nanoparticles produced have a hydrodynamic radius of 20–25 nm.

The amount of singlet oxygen (¹O₂) produced by Ru(dpp(SO₃)₂)₃ as been measured using anthracene-9,10-dipropionic acid (ADPA). A kinetic model for the disappearance of ADPA, by steady state irradiation of Ru(dpp(SO₃)₂)₃ at 465 nm, has been developed taking also into account a consumption not mediated by ¹O₂. This direct consumption of ADPA is evaluated by irradiating in the presence of NaN₃ and is about 30% of the total. All the experimental results are very well described by the model developed, both for free Ru(dpp(SO₃)₂)₃ and with this dye incorporated in the nanoparticles.

It is found that the polyacrylamide matrix does not quench the ¹O₂ produced, allowing it to reach the external solution of the nanoparticles and react with ADPA. When the matrix possesses amine groups, AFPAA, the amount of ¹O₂ that reacts with ADPA is slightly reduced, 60%, but most of the ¹O₂ produced can still leave the particles and react with external molecules. The particles produced may therefore be used as sources of ¹O₂ in photodynamic therapy (PTD) of cancers. The fact that those nanoparticles do not quench significantly the ¹O₂ makes possible the future development of ¹O₂ sensors based on PAA nanoparticles with the appropriate sensor molecule enclosed.     

Nanoscale Calorimetry Using a Suspended Bridge Configuration

Abstract A new setup for small-scale differential scanning calorimetry (DSC) studies based on a suspended bridge configuration is presented. The new setup has three major advantages over previously reported DSC setups: 1) superior temperature uniformity in the bridge cross section; 2) less heat loss to the surroundings by at least two orders of magnitude; and 3) a faster transient response by three orders of magnitude. This paper includes a thermal analysis to support these improvements. A major contribution of the new thermal analysis over previous reports is the inclusion of the thermal mass of the substrate in calculations, which makes thermal design more detailed, dramatically affecting accuracy and sensitivity in measurements. Furthermore, the new thermal analysis more accurately accounts for heat loss to the substrate and the surroundings in efforts to resolve suspected inconsistencies in previously reported data. Experimental validation of the new setup is presented by measuring the specific heat of thin layers of Si0₂ and CoFe. The specific heat of Si0₂ was found to be 2.2 times 10⁶ Jm ^-3 K^-1 which is nearly 10% different from the literature values of bulk specimens. For CoFe, the specific heat value of 3.16 x 10⁶ Jm ^-3 K^-1 is obtained using differential Cu/Si0₂ and Cu/Si0₂/CoFe structures compared to the value of 3.5 times 10⁶ Jm ^-3 K^-1 obtained using single CoFe suspended structure.     

An optimal multiplication algorithm on reconfigurable mesh

An O(1) time algorithm to multiply two K-bit binary numbers using an N×N bit-model of reconfigurable mesh is shown. It uses optimal mesh size and it improves previously known results for multiplication on the reconfigurable mesh. The result is obtained by using novel techniques for data representation and data movement and using multidimensional Rader Transform. The algorithm is extended to result in AT² optimality over 1⩽t⩽√N in a variant of the bit-model of VLSI     

L2 vector median filters on arrays with reconfigurableoptical buses

In spite of their good filtering characteristics for vector-valued image processing, the usability of vector median filters is limited by their high computational complexity. Given an N × N image and a W × W window, the computational complexity of vector median filter is O(W⁴N²). In this paper, we design three fast and efficient parallel algorithms for vector median filtering based on the 2-norm (L₂) on the arrays with reconfigurable optical buses (AROB). For 1 ⩽ p ⩽ W ⩽ q ⩽ N, our algorithms run in O(W⁴ log W/p⁴), O(W²N²/p ⁴q² log W) and O(1) times using p⁴N² / log W, p⁴q² / log W, and W⁴N² log N processors, respectively. In the sense of the product of time and the number of processors used, the first two results are cost optimal and the last one is time optimal     

Constructing Euclidean minimum spanning trees and all nearestneighbors on reconfigurable meshes

A reconfigurable mesh, R-mesh for short, is a two-dimensional array of processors connected by a grid-shaped reconfigurable bus system. Each processor has four I/O ports that can be locally connected during execution of algorithms. This paper considers the d-dimensional Euclidean minimum spanning tree (EMST) and the all nearest neighbors (ANN) problem. Two results are reported. First, we show that a minimum spanning tree of n points in a fixed d-dimensional space can be constructed in O(1) time on a √(n³)×√(n³) R-mesh. Second, all nearest neighbors of n points in a fixed d-dimensional space can be constructed in O(1) time on an n×n R-mesh. There is no previous O(1) time algorithm for the EMST problem; ours is the first such algorithm. A previous R-mesh algorithm exists for the two-dimensional ANN problem; we extend it to any d-dimensional space. Both of the proposed algorithms have a time complexity independent of n but growing with d. The time complexity is O(1) if d is a constant     

On the type of a polynomial f, when f(0)f−f(0)f is a monomial

A polynomial is said to be of type (p₁, p₂, p₃) relative to a directed line in the complex plane if, counting multiplicities, it has p₁ zeros to the left of, p₂ zeros on, and p₃ zeros to the right of the line. In this paper we determine explicitly the types of all polynomials belonging to a very restricted (but infinite) family of polynomials. A polynomial ƒ belongs to this family if and only if its coefficients are such that the polynomial ƒ^*(0)ƒ(z)−ƒ(0) ƒ^*(z) is a monomial; here ƒ^* denotes the reflection of ƒ in the directed line.

A special case of the present result appeared in an earlier publication.     

Fast iterative computation of optimal two-blockH∞-norm

The two-block H^∞ optimization problem is discussed, in which the most computationally demanding work is the computation of the optimal H^∞ norm denoted by γ₀. The problem of computing γ₀ can be considered as that of finding a γ such that μ(γ) is equal to 1. Some new properties of μ(γ) are revealed and studied. Based on these properties and those found by C.-C. Chu and J. Doyle (1985) and Z.Z. Wang and J.B. Pearson (1984), a very fast computational algorithm for finding γ₀ is proposed     

Fabrication of semiconducting YBaCuO surface-micromachinedbolometer arrays

Thermal infrared detectors require thermal isolation to permit the infrared-sensitive material to integrate the incident photon energy and thereby obtain high responsivity and detectivity. This paper describes the fabrication of semiconducting YBaCuO microbolometer arrays into thermal isolation structures by employing Si surface-micromachining techniques. An isotropic HF:HNO₃ etch was used to remove the underlying Si substrate from the front-side of the wafer and suspend SiO ₂ membranes into 1×10 pixel-array structures. The infrared-sensitive material, YBaCuO, was subsequently deposited onto the thermal isolation structures and patterned to form the detector arrays. The high-temperature coefficient of resistance and low noise of semiconducting YBaCuO at room temperature is attractive for uncooled infrared detection. The fabrication process was conducted entirely at room temperature. In this manner, infrared detectors are fabricated in a process that is compatible with CMOS technology to allow for the integration with on-chip signal processing circuitry. The end result is low-cost infrared-detector arrays for night vision in a variety of applications including transportation and security. Preliminary results show a temperature coefficient of resistance above 3%, voltage responsivity close to 10⁴ V/W, and detectivity over 10⁷ cm·Hz^1/2/W at a bias current of 0.79 μA     

Strongly buckled square micromachined membranes

The buckling of compressively prestressed square membranes with built-in edges is investigated experimentally and analyzed theoretically. The buckling depends weakly on Poisson's ratio and essentially is a function of the reduced prestrain, ε¯₀ =ε₀a²/h², where ε₀ is the physical prestrain, a is the width, and h is the thickness of the membrane. As ε¯₀ becomes increasingly negative, the membrane undergoes two symmetry breaking buckling transitions. Beyond the first transition occurring at ε¯_cr1, the buckling profile has all the reflection and rotation symmetries of a square. The reflection symmetries are lost through a second instability transition at ε¯_cr2. The bifurcation points, ε¯_cr1 and ε¯_cr2, and buckling profiles were calculated using analytical energy minimization and nonlinear finite-element simulation. Both methods agree. The buckling of micromachined plasma-enhanced chemical vapor deposition silicon nitride membranes on a silicon wafer is interpreted in terms of the theoretical results. Good matching between measured and calculated buckling profiles is found. The extracted strain values are consistent irrespective of the size and buckling mode of the membranes. From the average strain across the wafer ε₀=-3.50×10^-4 and complementary wafer curvature measurements, a Young's modulus of 130 GPa is deduced. Methods for the straightforward extraction of ε₀ from experimental center deflections of buckled square membranes are described     

量子化学方法研究阴离子表面活性剂在气液界面上的吸附

用量子化学方法中的密度泛函理论,在B3LYP/6-3IG水平上,对十二烷基硫酸钠（SDS）阴离子表面活性剂与水分子形成的水合物CH₃（CH₂）₁₁OSO₃ˉ（H₂O）_n（n=0～7）进行结构优化和频率计算。从分子水平上研究了CH₃（CH₂）₁₁OSO₃ˉ在气液界面上与水分子的相互作用。计算结果表明:（1）7个水分子与极性头均采用1:1型和2:1型,即极性头中一个氧原子或2个氧原子与水分子以氢键形式构成水合层;（2）CH₃（CH₂）₁₁OSO₃中的氧原子与水分子中的氧原子最短氢键的键长（O-O键长）在0.27～0.31 nm之间,H…O键长在0.19～0.21 nm之间,O-H…O键角在140°～167°之间,均属于中强氢键:（3）水合物R（S-O）平均键长比表面活性剂单体分子分别增长了,说明形成水合物后S-O间的键减弱;（4）结合能D₀从64.04 kJ/mol增加到.428.29 kJ/mol,说明随着水分子数的增加,所获得的7种水合物的稳定性依次增强,表明最终形成的水合层是稳定的:（5）随着水分子数增加疏水基链长收缩,亲水基总电荷增加,C12-O13-S14的键角增大;（6）由于烷烃链带有了弱电荷,使胶束内核带有了部分极性,此种极性介于烷烃油相和水相的极性之间,利于表面活性剂在溶液中的聚集。     

Fast and processor efficient parallel matrix multiplicationalgorithms on a linear array with a reconfigurable pipelined bus system

We present efficient parallel matrix multiplication algorithms for linear arrays with reconfigurable pipelined bus systems (LARPBS). Such systems are able to support a large volume of parallel communication of various patterns in constant time. An LARPBS can also be reconfigured into many independent subsystems and, thus, is able to support parallel implementations of divide-and-conquer computations like Strassen's algorithm. The main contributions of the paper are as follows. We develop five matrix multiplication algorithms with varying degrees of parallelism on the LARPBS computing model; namely, MM₁, MM ₂, MM₃, and compound algorithms C₁(ϵ)and C₂(δ). Algorithm C₁(ϵ) has adjustable time complexity in sublinear level. Algorithm C₂(δ) implies that it is feasible to achieve sublogarithmic time using σ(N³) processors for matrix multiplication on a realistic system. Algorithms MM₃, C₁(ϵ), and C₂(δ) all have o(𝒩³) cost and, hence, are very processor efficient. Algorithms MM₁, MM₃, and C₁(ϵ) are general-purpose matrix multiplication algorithms, where the array elements are in any ring. Algorithms MM₂ and C₂(δ) are applicable to array elements that are integers of bounded magnitude, or floating-point values of bounded precision and magnitude, or Boolean values. Extension of algorithms MM ₂ and C₂(δ) to unbounded integers and reals are also discussed     

McClellan transformation and the construction of biorthogonal wavelet bases of LR

Bidimensional wavelet bases are constructed by means of McClellan's transformation applied to a pair of one-dimensional biorthogonal wavelet filters. It is shown that under some conditions on the transfer function F(ω₁,ω₂) associated to the McClellan transformation and on the dilation matrix D, it is possible to construct symmetric compactly supported biorthogonal wavelet bases of L²(R²). Finally, the construction method is illustrated by means of numerical examples.     

Prefix computations on a generalized mesh-connected computer withmultiple buses

The mesh-connected computer with multiple buses (MC-CMB) is a well-known parallel organization, providing broadcast facilities in each row and each column. In this paper, we propose a 2D generalized MCCMB (2-GMCCMB) for the purpose of increasing the efficiency of executing some important applications of prefix computations such as solving Linear recurrences and tridiagonaI systems, etc. A k₁n₁ ×k₁n₂ 2-GMCCMB is constructed from a k ₁n₁×k₁n₂ mesh organization by enhancing the power of each disjoint n₁×n₂ submesh with multiple buses (sub-2-MCCMB). Given n data, a prefix computation can be performed in O(n^1/10) time on an n^3/5×n^2/5 2-GMCCMB, where each disjoint sub-2-MCCMB is of size n^1/2×n^3/10. This time bound is faster than the previous time bound of O(n^1/8) for the same computation on an n^5/8×n^3/8 2-MCCMB. Furthermore, the time bound of our parallel prefix algorithm can be further reduced to O(n^1/11) if fewer processors are used. Our result can be extended to the d-dimensional GMCCMB, giving a time bound of O(n¹ (d2(d)+d)/) for any constant d; here, we omit the constant factors. This time bound is less than the previous time bound of O(n¹(d2(d))/) on the d-dimensional MCCMB     

An optimal algorithm for the angle-restricted all nearest neighborproblem on the reconfigurable mesh, with applications

Given a set S of n points in the plane and two directions r₁ and r₂, the Angle-Restricted All Nearest Neighbor problem (ARANN, for short) asks to compute, for every point p in S, the nearest point in S lying in the planar region bounded by two rays in the directions r₁ and r₂ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size n×n. Our algorithm is optimal in the sense that Ω(n²) processors are necessary to solve the ARANN problem in O(1) time. By using our ARANN algorithm, we can provide O(1) time solutions to the tasks of constructing the Geographic Neighborhood Graph and the Relative Neighborhood Graph of n points in the plane on a reconfigurable mesh of size n×n. We also show that, on a somewhat stronger reconfigurable mesh of size n×n², the Euclidean Minimum Spanning Tree of n points can be computed in O(1) time