Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We study the preconditioning of symmetric indefinite linear systems of equations that arise in interior point solution of linear optimization problems. The preconditioning method that we study exploits the block structure of the augmented matrix to design a similar block structure preconditioner to improve the spectral properties of the resulting preconditioned matrix so as to improve the convergence rate of the iterative solution of the system. We also propose a two-phase algorithm that takes advantage of the spectral properties of the transformed matrix to solve for the Newton directions in the interior-point method. Numerical experiments have been performed on some LP test problems in the NETLIB suite to demonstrate the potential of the preconditioning method discussed.

Implicit-factorization preconditioning and iterative solvers for regularized saddle-point systems

We consider conjugate-gradient like methods for solving block symmetric indefinite linear systems that arise from saddle-point problems or, in particular, regularizations thereof. Such methods require preconditioners that preserve certain sub-blocks from the original systems but allow considerable flexibility for the remaining blocks. We construct a number of families of implicit factorizations that are capable of reproducing the required sub-blocks and (some) of the remainder. These generalize known implicit factorizations for the unregularized case. Improved eigenvalue clustering is possible if additionally some of the noncrucial blocks are reproduced. Numerical experiments confirm that these implicit-factorization preconditioners can be very effective in practice.

Diacylglycerol-induced protection against injury during ischemia and reperfusion can be achieved without activation of protein kinase C in the rat heart: Comparative studies with ischemic preconditioning

The role of protein kinase C (PKC) activation in ischemic preconditioning remains controversial. Since diacylglycerol is the endogenous activator of PKC and as such might be expected cardioprotective, we have investigated whether: (i) the diacylglycerol analog 1,2-dioctanoyl-sn-glycerol (DOG) can protect against injury during ischemia and reperfusion; (ii) any effect is mediated via PKC activation; and (iii) the outcome is influenced by the time of administration. Isolated rat hearts were perfused with buffer at 37°C and paced at 400 bpm. In Study 1, hearts (n=6/group) were subjected to one of the following: (1) 36 min aerobic perfusion (controls); (2) 20 min aerobic perfusion plus ischemic preconditioning (3 min ischemia/3 min reperfusion+5 min ischemia/5 min reperfusion); (3) aerobic perfusion with buffer containing DOG (10 μM) given as a substitute for ischemic preconditioning; (4) aerobic perfusion with DOG (10 μM) during the last 2 min of aerobic perfusion. All hearts then were subjected to 35 min of global ischemia and 40 min reperfusion. A further group (5) were perfused with DOG (10 μM) for the first 2 min of reperfusion. Ischemic preconditioning improved postischemic recovery of LVDP from 24±3% in controls to 71±2% (P<0.05). Recovery of LVDP also was enhanced by DOG when given just before ischemia (54±4%), however, DOG had no effect on the recovery of LVDP when used as a substitute for ischemic preconditioning (22±5%) or when given during reperfusion (29±6%). In Study 2, the first four groups of study were repeated (n=4–5/group) without imposing the periods of ischemia and reperfusion, instead hearts were taken for the measurement of PKC activity (pmol/min/mg protein±SEM). PKC activity after 36 min in groups (1), (2), (3) and (4) was: 332±102, 299±63, 521±144, and 340±113 and the membrane:cytosolic PKC activity ratio was: 5.6±1.5, 5.3±1.8, 6.6±2.7, and 3.9±2.1 (P=NS in each instance). In conclusion, DOG is cardioprotective but under the conditions of the present study is less cardioprotective than ischemic preconditioning, furthermore the protection does not appear to necessitate PKC activation prior to ischemia.

Phorbol ester, but not ischemic preconditioning, activates protein kinase D in the rat heart

The signal transduction pathways that mediate the cardioprotective effects of ischemic preconditioning remain unclear. Here we have determined the role of a novel kinase, protein kinase D (PKD), in mediating preconditioning in the rat heart. Isolated rat hearts (n=6/group) were subjected to either: (i) 36 min aerobic perfusion (control); (ii) 20 min aerobic perfusion plus 3 min no-flow ischemia, 3 min reperfusion, 5 min no-flow ischemia, 5 min reperfusion (ischemic preconditioning); (iii) 20 min aerobic perfusion plus 200 nmol/l phorbol 12-myristate 13-acetate (PMA) given as a substitute for ischemic preconditioning. The left ventricle then was excised, homogenized and PKD immunoprecipitated from the homogenate. Activity of the purified kinase was determined following bincubation with [γ32P]-ATP±syntide-2, a substrate for PKD. Significant PKD autophosphorylation and syntide-2 phosphorylation occurred in PMA-treated hearts, but not in control or preconditioned hearts. Additional studies confirmed that recovery of LVDP was greater and initiation of ischemic contracture and time-to-peak contracture were less, in ischemic preconditioned hearts compared with controls (P<0.05). Our results suggest that the early events that mediate ischemic preconditioning in the rat heart occur via a PKD-independent mechanism.

Conditioning and preconditioning of the variational data assimilation problem

Numerical weather prediction (NWP) centres use numerical models of the atmospheric flow to forecast future weather states from an estimate of the current state. Variational data assimilation (VAR) is used commonly to determine an optimal state estimate that miminizes the errors between observations of the dynamical system and model predictions of the flow. The rate of convergence of the VAR scheme and the sensitivity of the solution to errors in the data are dependent on the condition number of the Hessian of the variational least-squares objective function. The traditional formulation of VAR is ill-conditioned and hence leads to slow convergence and an inaccurate solution. In practice, operational NWP centres precondition the system via a control variable transform to reduce the condition number of the Hessian. In this paper we investigate the conditioning of VAR for a single, periodic, spatially-distributed state variable. We present theoretical bounds on the condition number of the original and preconditioned Hessians and hence demonstrate the improvement produced by the preconditioning. We also investigate theoretically the effect of observation position and error variance on the preconditioned system and show that the problem becomes more ill-conditioned with increasingly dense and accurate observations. Finally, we confirm the theoretical results in an operational setting by giving experimental results from the Met Office variational system.

Rapid preconditioning of data for accelerating convex hull algorithms

Given a dataset of two-dimensional points in the plane with integer coordinates, the method proposed reduces a set of n points down to a set of s points s ≤ n, such that the convex hull on the set of s points is the same as the convex hull of the original set of n points. The method is O(n). It helps any convex hull algorithm run faster. The empirical analysis of a practical case shows a percentage reduction in points of over 98%, that is reflected as a faster computation with a speedup factor of at least 4.

Conditioning and preconditioning of the optimal state estimation problem

Optimal state estimation is a method that requires minimising a weighted, nonlinear, least-squares objective function in order to obtain the best estimate of the current state of a dynamical system. Often the minimisation is non-trivial due to the large scale of the problem, the relative sparsity of the observations and the nonlinearity of the objective function. To simplify the problem the solution is often found via a sequence of linearised objective functions. The condition number of the Hessian of the linearised problem is an important indicator of the convergence rate of the minimisation and the expected accuracy of the solution. In the standard formulation the convergence is slow, indicating an ill-conditioned objective function. A transformation to different variables is often used to ameliorate the conditioning of the Hessian by changing, or preconditioning, the Hessian. There is only sparse information in the literature for describing the causes of ill-conditioning of the optimal state estimation problem and explaining the effect of preconditioning on the condition number. This paper derives descriptive theoretical bounds on the condition number of both the unpreconditioned and preconditioned system in order to better understand the conditioning of the problem. We use these bounds to explain why the standard objective function is often ill-conditioned and why a standard preconditioning reduces the condition number. We also use the bounds on the preconditioned Hessian to understand the main factors that affect the conditioning of the system. We illustrate the results with simple numerical experiments.

PKC-dependent activation of p46/p54 JNKs during ischemic preconditioning in conscious rabbits.

A conscious rabbit model was used to study the effect of ischemic preconditioning (PC) on stress-activated kinases [c-Jun NH(2)-terminal kinases (JNKs) and p38 mitogen-activated protein kinase (MAPK)] in an environment free of surgical trauma and attending external stress. Ischemic PC (6 cycles of 4-min ischemia/4-min reperfusion) induced significant activation of protein kinase C (PKC)-epsilon in the particulate fraction, which was associated with activation of p46 JNK in the nuclear fraction and p54 JNK in the cytosolic fraction; all of these changes were completely abolised by the PKC inhibitor chelerythrine. Selective enhancement of PKC-epsilon activity in adult rabbit cardiac myocytes resulted in enhanced activity of p46/p54 JNKs, providing direct in vitro evidence that PKC-epsilon is coupled to both kinases. Studies in rabbits showed that the activation of p46 JNK occurred during ischemia, whereas that of p54 JNK occurred after reperfusion. A single 4-min period of ischemia induced a robust activation of the p38 MAPK cascade, which, however, was attenuated after 5 min of reperfusion and disappeared after six cycles of 4-min ischemia/reperfusion. Overexpression of PKC-epsilon in cardiac myocytes failed to increase the p38 MAPK activity. These results demonstrate that ischemic PC activates p46 and p54 JNKs via a PKC-epsilon-dependent signaling pathway and that there are important differences between p46 and p54 JNKs with respect to the subcellular compartment (cytosolic vs. nuclear) and the mechanism (ischemia vs. reperfusion) of their activation after ischemic PC.

Preconditioning 2D integer data for fast convex hull computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.