Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

A new polar nephelometer for measurement of atmospheric aerosols

The angular dependence of light scattered by aerosol particles in the atmosphere—the aerosol phase function—is one of the key properties of every radiative transfer and climate model. Side-scattering in the atmosphere is currently believed to be underestimated by most of the radiative transfer models in certain cases. The aerosol phase function can be measured with polar nephelometers.An innovative polar nephelometer able to measure the phase function of ambient aerosol directly is presented in this publication. The performance of the device was simulated completely using ray-tracing techniques. The results of these simulations are used to interpret the measurement data precisely. The measurements with the new polar nephelometer are fully automated. The quality of the measurement results was verified using different approaches. The values of the statistical and systematic error in measuring atmospheric aerosol are about 4% each. Scattering angles from 10° to 160° were measured and it is shown that with the same design this range can be extended to 3-177° in steps of 0.16° with an aperture of less than 1.8°.Measurements of the aerosol phase function are presented and compared with data taken with an integrating nephelometer and measurements of the particulate matter concentration. All data correlate very well. The described polar nephelometer can measure the phase function and the scattering coefficient of atmospheric aerosol with high accuracy and can be used for continuous monitoring measurements as well as in field campaigns.     

Methodological reflections on a three-step-design combining observation,stimulated recall and interview

In this paper a tripartite qualitative design combining abservation, stimulated recall and interview is presented and discussed. This three-step-design makes it possible to get insight into the interaction of internal and external processes when solving mathematical tasks. The data analysis depends on the research question and the methodological approach. In the light of two research projects in mathematics education two different methods of data analysis are presented and methodologically reflected.     

Synthese und Eigenschaften von Sr3Mo1.5Zn0.5O7‐δ, einer Phase mit perowskitverwandter Schichtstruktur

Synthesis and Properties of the Layered Perovskite Phase Sr₃Mo_1.5Zn_0.5O_7‐δ The new layered perovskite phase Sr₃Mo_1.5Zn_0.5O_7‐δ was synthesized by solid state reaction using a Zn/ZnO oxygen buffer. The crystal structure was refined from X‐ray powder pattern by the Rietveld method. The compound crystallizes tetragonal in the space group I4/mmm (no. 139) with the lattice parameters a = 3.9631(3) Å, c = 20.583(1) Å. An oxygen deficiency corresponding to δ ≈ 0.25 was determinated, indicating the presence of molybdenum in mixed valence (Mo⁴⁺ and Mo⁶⁺).     

catena‐Poly[tetra­kis(3‐phenyl­propyl­ammonium) [iodo­plumbate(II)‐tri‐μ‐iodo‐plumbate(II)‐tri‐μ‐iodo‐iodo­plumbate(II)‐di‐μ‐iodo]]

The title compound, {(C₉H₁₄N)₄[Pb₃I₁₀]}_n, crystallizes as an organic–inorganic hybrid. As such, the structure consists of a two‐dimensional inorganic layer of [Pb₃I₁₀]_n⁴ⁿ⁻ ions extending along [100]. The asymmetric unit contains two independent Pb atoms, viz. one in a general position and the other on an inversion centre. Each Pb atom is octa­hedrally coordinated by six iodide ions and exhibits both face‐ and corner‐sharing with adjacent atoms in the inorganic layer. These anionic layers alternate with 3‐phenyl­propyl­ammonium cations, which hydrogen bond to the iodides. Simple face‐to‐edge σ–π stacking inter­actions are observed between the aromatic rings that stabilize the overall three‐dimensional structure. This net structure has only been observed five times previously.     

Chip-calorimeter for small samples

A method for measuring heat capacities of small samples using a chip-calorimeter and a heat pulse technique is described. The theoretical background to calculate the heat transport properties and the heat capacity of the sample from the pulse response function is given. Problems and potentials of the method are discussed. An example is given.     

A p-version finite element method for nonlinear elliptic variational inequalities in 2D

This article introduces and analyzes a p-version FEM for variational inequalities resulting from obstacle problems for some quasi-linear elliptic partial differential operators. We approximate the solution by controlling the obstacle condition in images of the Gauss–Lobatto points. We show existence and uniqueness for the discrete solution u _p from the p-version for the obstacle problem. We prove the convergence of u _p towards the solution with respect to the energy norm, and assuming some additional regularity for the solution we derive an a priori error estimate. In numerical experiments the p-version turns out to be superior to the h-version concerning the convergence rate and the number of unknowns needed to achieve a certain exactness of the approximation.     

Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥ ₂ ² , we extend results which hold for sufficiently smooth functionsF to the nonsmooth case. In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1+p.