text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

# Projected increases in western US forest fire despite growing fuel constraints

## Abstract

Escalating burned area in western US forests punctuated by the 2020 fire season has heightened the need to explore near-term macroscale forest-fire area trajectories. As fires remove fuels for subsequent fires, feedbacks may impose constraints on the otherwise climate-driven trend of increasing forest-fire area. Here, we test how fire-fuel feedbacks moderate near-term (2021–2050) climate-driven increases in forest-fire area across the western US. Assuming constant fuels, climate–fire models project a doubling of  forest-fire area compared to 1991–2020. Fire-fuel feedbacks only modestly attenuate the projected increase in forest-fire area. Even models with strong feedbacks project increasing interannual variability in forest-fire area and more than a two-fold increase in the likelihood of years exceeding the 2020 fire season. Fuel limitations from fire-fuel feedbacks are unlikely to strongly constrain the profound climate-driven broad-scale increases in forest-fire area by the mid-21st century, highlighting the need for proactive adaptation to increased western US forest-fire impacts.

## Introduction

The annual area burned by forest fires in the western United States (US) has increased ten-fold over the past half-century1, punctuated by the record 2020 western US fire season that produced widespread negative effects2. Several anthropogenic factors underpin growing wildland fire area, including historically high fuel loads due to a century of fire suppression and outlawing of Indigenous burning; less direct suppression tactics to support firefighter safety, and increased fuel aridity due to human-caused climate change3,4,5,6. While the influence of these factors varies geographically as a function of both biophysical and human–environment interactions, climate variability expressed through fuel dryness is the dominant interannual driver of macroscale burned area across fuel-rich biomes in the western US and globe7.

Increasing fuel aridity (F) and fire-weather extremes with continued climate change portend increased wildland fire activity where biomass is abundant and flammability is a primary constraint8,9, including in western US forests1,3. Warming directly enhances fuel aridity by increasing the vapor pressure deficit (VPD) as well as reducing snowpack in montane regions, which collectively intensify and lengthen the fire season. Decreased summer precipitation in parts of the western US in recent decades has further increased fire-season F10. Most climate projections show increased F across the western US11,12 and longer fire-weather seasons13 that facilitate increased occurrence of fire-weather extremes in the autumn in California14.

One key limitation in projecting trajectories of future fire is the degree to which decreasing available fuel will limit fire growth, suggesting eventual nonlinearities in contemporary climate–fire relationships15,16. Statistical models where climate alone drives changes in the burned area suggest massive future increases17. Such models assume sufficient fuels remain to support future burning, but there is strong evidence that increased forest-fire area may initiate fire-fuel feedbacks that limit future burned area18 through the reduction of fuel biomass and extent, the ability of forested environments to carry fire15, and the alteration of post-fire-vegetation patterns and climate that may limit tree regeneration19. Herein, we track fire-fuel feedbacks through a term called L, which represents the fraction of contemporary forested land that is incapable of carrying forest fire in a given year because it has been modified by fire in the recent past (~30 years) or through semi-permanent loss of forest due to post-fire tree regeneration failure. Recently burned areas can sometimes reburn at much shorter timescales—particularly with low-severity fire20, in which case L will be less than the fraction of recently burned area. Fire can also create forest mosaics with reduced connectivity that are less prone to fire, in which case L exceeds the fraction of recently burned area. Studies have shown that fire-fuel feedbacks can moderate future changes in the burned area at local scales21. However, studies have not evaluated how fire-fuel feedbacks and climate will affect future fire activity at the scale of the entire western US forest area or the sensitivity of these projections to uncertainties in the duration and strength of the fire-fuel feedbacks.

Here, we use several possible forms of dynamic models that account for various fire-fuel feedbacks, a static model that does not incorporate vegetation feedbacks and assumes constant fuel extent, and projections of future climate change to bracket projected changes in near-term (2021–2050) western US forest-fire area. We additionally evaluate projected changes in the interannual variability of forest-fire area, the likelihood of years with a forest-fire area exceeding that observed in the record-breaking 2020 fire season, as well as the likelihood of years with a forest-fire area below the 1991–2020 median. We limit projections of the forest-fire area to 2050 acknowledging the greater uncertainty in vegetation dynamics, human behavior, and climate trajectories beyond mid-century. Given the wide range of uncertainty in the fire-fuel feedbacks, we present several forms and strengths of fire-fuel feedbacks as guided by the ecological literature that accounts for (1) post-fire tree regeneration failure, (2) the form and strength of fuel limitations imposed by recent fire history, and (3) the modulation of the longevity of fuel limitations during drought18,22,23,24.

## Results

To project future fire, we first build a model of climate–fire relationships for the observational period and evaluate the model’s skill. There is a positive interannual correlation (r2 = 0.80) between F and the logarithm of western US forest-fire area during the modern satellite observational record (1984–2020; Fig. 1a and Supplementary Table 1). These extend the results of previous studies that found strong relationships between burned area and aridity in forested regions of the western US3,25,26,27. Notably, the nonlinear response of forest-fire area to F, suggests that each incremental increase in F leads to a greater response in forest-fire area than prior increases. The 1.0 σ increase in mean F from 1984–1999 to 2000–2020 coincided with a four-fold increase in the upper quartile of annual forest-fire area totals (Fig. 2a).

Cross-validation of the models over the observational period was performed to evaluate non-stationarity in relationships that may arise through exogenous factors and the applicability of empirical models to future conditions. Models built using various subsets of data (1984–2020, 1984–1999, 2000–2020) yield statistically indistinguishable regression parameters (e.g., Fig. 1a). Similarly, models trained on the first portion of the dataset were as skillful in predicting the forest-fire area in the second portion of the dataset (Supplementary Table 2). Results of this cross-validation exercise suggest that changes in fuel extent or other changes in human–environment factors during 1984–2020 did not significantly affect macroscale climate–fire relationships. Further, this cross-validation also suggests that such models can provide near-term predictive utility27.

Climate models project robust anthropogenic increases in fuel aridity for the next 30 years (Fig. 1b). Averaged across projections made by 30 climate models, F increases by 0.66 σ for 2021–2050 compared to 1991–2020 (+0.45 to +0.80 σ interquartile range of CMIP6 models), primarily because of warming-induced increases in evaporative demand.

Assuming no changes in fuel extent, our static model yields a doubling (30-model median increase of 107%) in the mean annual forest-fire area during 2021–2050 compared to that observed during 1991–2020 (Fig. 2b)—with the 2021–2050 cumulative forest-fire area equivalent to ~35% of contemporary forested area. While there is substantial intermodel variability, climate projections made by 26 of 30 models lead to at least a 50% increase in forest-fire area (Fig. 2b). We additionally show a two-fold increase in the interquartile range in the annual forest-fire area and a three-fold increase in the probability of years exceeding the record-breaking 2020 season (Fig. 3c, d). However, years with quiescent fire activity are also projected to remain semi-regular occurrences; approximately one-third of the years between 2021 and 2050 are projected to have less forest-fire area than the observed median annual forest-fire area during 1991–2020 (Fig. 3e).

Our dynamic models suggest that the area ineligible to burn because of past fire L declined over the twentieth century (Fig. 4), supporting the well-documented fire deficit and increase in forest biomass across western US forests from pre-colonization baselines due to fire suppression28. This decrease in L has heightened the sensitivity of the contemporary forest-fire area to F. Yet, our models suggest that the recent increase in the forest-fire area has reversed the twentieth-century decline in L.

The dynamic models that include a wide range of feedback strengths and durations only modestly reduce the magnitude of the projected increase in forest-fire area (Fig. 3a, b). Dynamic models with weak and moderate fire-fuel feedbacks show increases in the mean annual forest-fire area of 82–90% and 63–75%, respectively, compared to the 107% increase projected by the static model. The dynamic model with the strongest fire-fuel negative feedback yields a 46% increase in the forest-fire area during 2021–2050 compared to 1991–2020 observations. Projected increases in forest-fire area facilitate increased L (Fig. 4), increasingly limiting the total forested area eligible to burn21,24. Dynamic models also show an increase in year-to-year variability in the forest-fire area and an increase in the probability of years exceeding the 2020 fire season (Fig. 3b, c), albeit with smaller changes than projected by the static model. Finally, the relative effects of dynamic fire-vegetation feedbacks on future fire statistics are relatively insensitive to choices in the form of the feedbacks, parameter values, and the index used to measure aridity F (e.g., CWD). For example, a formulation of L that assumes a weak fire-vegetation feedback results in 14–19% reductions in the future forest-fire area relative to the static model’s projection across a range of alternative model parameterizations and inputs (Supplementary Table 3).

## Discussion

Our findings suggest that the continued increase of western US forest-fire area due to drying fuels will only be moderately allayed by the eventual constraints on fuel extent and biomass from fire-fuel feedbacks. Even the strongest feedbacks in our models yield significant increases in forest-fire area, probability of extreme fire years, and year-to-year variability in forest-fire area. The projected increase in forest-fire area materializes from thermodynamic responses to anthropogenic climate change1,27 and the exponential response of forest-fire area to fuel aridity in this contemporary human–environment system. Larger increases in the forest-fire area were found with indices of atmospheric aridity F that do not explicitly include precipitation (e.g., VPD; Supplementary Figs. 1 and 2).

Our study focuses on the aggregate of the forest-fire area in the western US given the robust and dominant relationship between aggregate area burned and climate, and because the leading pattern of variability in fire-season aridity spans the entire western US (Supplementary Fig. 3). Coupled fire-vegetation models with greater granularity may provide richer information by incorporating complex feedback processes21,24,29. However, these models are computationally expensive to run for continental domains. Likewise, while we evaluate the strength and longevity of these fire-fuel feedbacks, fire regime characteristics can also be shaped by other disturbance agents leading up to and following fire events, including insects, drought mortality, windthrow, invasive annual grasses, or anthropogenic disturbances such as harvest. While each disturbance agent can have sizeable impacts on forest mortality30, their interactions with fire are mixed and context-dependent31 confounding a credible way of incorporating them herein. We note land area in L is not immune to fire; rather, such lands in post-fire successional trajectories may support grassland and shrubland fire that are not accounted for here. Relatively larger increases in the forested-fire area due to anthropogenic climate change are postulated in mesic flammability-limited forest systems than in drier forest systems16,32.

Lastly, our focus herein is on the forest-fire area; changes in area burned in non-forested lands may differ markedly from those presented here16. Anthropogenic modification of fire regimes, including fire suppression, has increased the proportion of western US forests available to burn, particularly at higher intensity, over the twentieth century. Recent repeat forest fires have constrained fire growth and reduced fire severity33,34,35, yet macroscale fuel constraints have not yet become evident at the scale of the western US forest area. These feedbacks may become increasingly relevant with increased fire, but the timing, magnitude, and efficacy of such feedbacks are highly uncertain and warrant further study. That being said, our results suggest feedbacks between fire and fuel alone will very likely be insufficient to reverse the rapid and ongoing increases in annual western US forest-fire area in the coming decades. Notably, however, the binary definition of fire area does not capture the local variation in fire intensity, and some portion of increasing fire area will undoubtedly be the lower-intensity, ecologically beneficial fire that restores fire-adapted, dry forest ecosystems.

Western North American forests evolved with fire, however, such fire was characteristically far different than the contemporary period and included thousands of cultural fires set by Indigenous people that burned over days to months36. Continued increases in the recent trend of megafires that are driving greater forest-fire area have negative socio-ecological consequences including fatalities, destruction of infrastructure37, and ecosystem impacts such as widespread tree regeneration failure38. Absent broad mitigation and adaptation, losses will increase, highlighting the need for strategies to ameliorate the trajectory of escalating fire impacts39. In addition to reducing fossil fuel emissions to slow the impact of increasing aridity, our dynamic models complement the substantial body of literature showing that locally appropriate land management strategies designed to intentionally increase L may also slow increases in negative fire impacts40. Strategies demonstrated to be effective in increasing L include mechanical fuel reduction and expanding the use of prescribed fire and managed wildfire, particularly when conditions are conducive (e.g., F is relatively low) during quiescent fire seasons, which we show will continue to occur despite climate change. While the forest-fire area was more than an order of magnitude than the forested area treated with prescribed fire in the contemporary record41, scaling up the use of prescribed fire may assist in curtailing negative fire effects through increased L. However, further analyses are needed to evaluate potential changes in windows of opportunity for using prescribed fire subject to biophysical (e.g., fuels, weather) and logistical constraints.

It appears unavoidable that absent a massive intervention to modify the intensity and mitigate negative impacts, the western US forest-fire area will continue to increase in the coming decades. Recent years indicate this will likely occur primarily through the occurrence of problematic megafires, even as fuel-limitation feedbacks begin to slow this increase. It is also critical to recognize that not all fire has negative outcomes42, and mitigation and adaptation strategies can alter the outcomes of increasing fire. Dynamic models with stronger feedbacks yielded forest-fire area similar to estimates from the pre-colonization era—levels of the forest-fire area under which modern forest ecosystems evolved. As most area burned is low or moderate-severity fire, such increases in fire activity could ultimately facilitate ecosystem restoration, but mitigating fire disasters will be crucial. Managers and policymakers can carefully consider where management actions are most beneficial, the challenges of implementing such actions, and how these approaches scale geographically to meaningfully alter widespread outcomes43.

## Methods

### Data sets

Monthly climate data of maximum and minimum temperature, dewpoint temperature, and precipitation at a 1/24th degree horizontal resolution from 1950 to 2020 was acquired from the Parameterized Regression on Independent Slopes Model (PRISM)44. Monthly surface downward shortwave radiation and 10-m wind speeds at a 0.25-degree horizontal resolution were acquired from ERA-545 for the same period and bilinearly interpolated to the PRISM grid. Monthly data for the same variables from a single ensemble member from each of 30 climate models participating in the Sixth Coupled Model Intercomparison Project (CMIP6) were acquired from the historical climate experiment for 1950–2014 and from the SSP2-45 experiment for 2015–2050 and interpolated to a common 1.0-degree horizontal resolution grid (Supplementary Table 4).

Following Abatzoglou and Williams, we calculated three proxies of aridity using monthly climate data: mean vapor pressure deficit (VPD), Penman-Monteith reference evapotranspiration (ETo), and climatic water deficit (CWD46, defined as ETo minus actual evapotranspiration3). We modified ETo to account for potential reduced stomatal conductance due to increasing atmospheric carbon dioxide, which reduces surface resistance to evapotranspiration. We made this modification following the method of Yang et al.47. Importantly, the effect of CO2 on surface resistance at the scale of the western US is highly uncertain and this method derives the strength of this effect from earth system models. Each index was calculated as follows. At each grid cell, we calculated mean Mar–Sep VPD, the sum of Mar–Sep ETo, and Jan-Dec CWD; each of these time series was standardized to the 1991–2020 baseline using z-score transformations to create a fuel aridity index f for each grid cell. The regionally averaged fuel aridity index F was calculated by first taking the average of f over grid cells that have a majority of land classified as forest or woodland in the LANDFIRE environmental site potential product48. We then re-standardized F relative to the 1991–2020 reference period and applied equidistant quantile mapping49 to each model. The latter ensures that the distributions of modeled Z match those of observed Z for the 1991–2020 period while preserving changes in Z from this reference period. Herein we used CWD for F because it presents a more balanced view of precipitation and atmospheric demand than VPD or ETo alone, exhibits strong links to the forest-fire area over the observational record, and has more conservative increases in fire under future climate (Supplementary Fig. 2). The variance explained in forest-fire area when defining F as VPD, ETo, and detrended CWD is presented in Supplementary Table 1. We note that our approach does not explicitly incorporate daily meteorology such as the number of dry days or critical fire-weather patterns10 beyond that already included in F.

Burned area data from wildland fires were acquired from Monitoring Trends in Burn Severity (MTBS) during 1984–201850 and from the version 6 MODIS burned area dataset during 2001–202051. The forested burned area was aggregated by lands classified as forest or woodland48. MTBS includes primarily fires ≥404 ha that comprises>95% of burned area in the region52. We further excluded areas in the unburned-to-low burn severity class53 as well as fires classified as prescribed burns in MTBS. Further, we did not include forested area treated by prescribed fire as a contemporary area for prescribed fire is more than an order of magnitude less than that of forest-fire area41. Forest-fire area estimates for 2019–2020 were obtained using adjusted burned areas from MODIS based on a linear model that relates MODIS and to the MTBS forest-fire area time series during the overlapping 2001–2018 period26.

### Experimental design

We focus on macroscale climate–fire models operating at the scale of the entire western US forested area. While there is value in spatially refined models, efforts to parameterize empirical relationships at localized scales can be limited by the stochastic nature of ignitions and fire weather—particularly in locations with long fire return intervals with zero-inflated distributions of annual burned area. Strong interannual relationships between fuel aridity and strain on national fire suppression resources shared across the region highlight the implicit value in considering larger spatial scales54. The macroscale approach is further justified because the leading mode of variability in fuel aridity across forested land is a commonly signed regionwide pattern that is strongly correlated (r2 = 0.79) to the logarithm of forest-fire area (Supplementary Fig. 3).

### Static model

Following previous empirical models of annual forest-fire area3,25, we first consider a static model of western US annual forest-fire area (FFA) based on F (fuel aridity) of the form:

$${{{{{\rm{log }}}}}}\left({{{{{{\mathrm{FFA}}}}}}}(t)\right)={\alpha }_{{{{{{\mathrm{s}}}}}}}+{\beta }_{{{{{{\mathrm{s}}}}}}}F\left(t\right)+{{{{{\rm{\varepsilon }}}}}},$$
(1)

where t is the year, αs and βs, are regression coefficients, and ε represents an error term. We use annual CWD for F as it accounts for precipitation and atmospheric demand, exhibits strong interannual relationships with FFA, and provide more conservative estimates of projected changes in aridity and thus area burned than other aridity metrics such as VPD3,7,12. The error term ε is drawn from the population of the log-residual of observed minus modeled FFA. This error term represents variability not captured in the FFA–F relationship (e.g., extreme fire-weather conditions, human ignitions) that is important for the full distribution of FFA.

### Dynamic models

The contemporary climate–fire relationship in Eq. 1 should persist with increased F until increased burned area and severity cause fuel limitations15. Fire-fuel feedbacks that alter the climate–fire relationship primarily occur through temporary reduction of fine fuels; such feedbacks can reduce the burning potential for approximately three decades post-fire38,55. Further, longer-lived reductions in the forest-fire area can occur when forests do not recover from fire and instead transition to non-forest vegetation that can still carry fire. However, constraints on the area burned imposed by fire-fuel feedbacks are weakened by concurrent drought, which allows the fire to propagate across sparser fuels, and can markedly shorten the window of reduced burning18.

We incorporate these effects through a term L, which represents the fraction of contemporary forested land that is incapable of carrying fire in a predominately forested environment in a given year, in a dynamic model of the form:

$${\log }\left(\frac{{{{{{{\mathrm{FFA}}}}}}}}{1-L\left(t\right)}\right)={\alpha }_{{{{{{\mathrm{d}}}}}}}+{\beta }_{{{{{{\mathrm{d}}}}}}}F\left(t\right)+{{{{{\rm{\varepsilon }}}}}},$$
(2)

where the response of log(FFA) to fuel aridity reduces as a function of L. We present various potential forms and strengths of fire-fuel feedbacks in L that are guided by the ecological literature and account for post-fire tree regeneration failure, fuel limitations imposed by recent fire history, and waning of fuel limitations during drought18,22,23,24. L is influenced by semi-permanent limitations due to failure of post-fire forest regeneration (Lrf), and temporary limitations due to recent fire history (Lf):

$$L\left(t\right)={L}_{{{{{{{\mathrm{rf}}}}}}}}\left(t\right)+{L}_{{{{{{\mathrm{f}}}}}}}(t).$$
(3)

Importantly, L is poorly constrained and likely varies in geographically and temporally complex ways18,34. For example, L can differ for a fixed fraction of recently burned forest. A relatively small L implies weak feedbacks allowing forests to more easily reburn. A relatively large L implies strong feedbacks, for example, where heterogeneous fire effects create patch mosaics that constrain fire spread even though there is ample fuel. Finally, the age threshold for L may decrease with continued climate change, with some indications that recent fires burned through forests <10 years post-fire.

### Post-fire tree regeneration failure Lrf

Summer soil moisture deficits in the years post-fire may reduce tree regeneration19,38. Absent reforestation, the failure of post-fire forest regeneration represents a semi-permanent reduction in forested land available to burn. Post-fire regeneration is strongly dependent on site-specific thresholds in growing-season moisture requirements23,56, burn severity and distance to the seed source, as well as species composition. We estimate the fraction (ρ) of forest that is permanently lost due to the failure of post-fire regeneration using the mean fuel aridity over the 3-year post-fire period (F3y) because protracted drought stress in the years immediately following fire has been shown to limit the establishment of some tree species57. This is done using a simple linear transform:

$$\rho (t)=\left\{\begin{array}{c}0,{F}_{3{{{{{\mathrm{y}}}}}}} < 1\\ \mu ({F}_{3{{{{{\mathrm{y}}}}}}}-1),1 \, < \, {F}_{3{{{{{\mathrm{y}}}}}}}\le 2\\ \,\mu ,{F}_{3{{{{{\mathrm{y}}}}}}} \, > \, 2\end{array}\right.,$$
(4)

where μ is set at 0.1 (Eq. 4 is plotted in Supplementary Fig. 4a). Hence, the fraction of forested land that is semi-permanently ineligible to carry forest fire because previously burned forest did not regenerate as forest (Lrf) is the cumulative sum of the product of annual FFA and ρ since 1984:

$${L}_{{{{{{{\mathrm{rf}}}}}}}}\left(t\right)=\mathop{\sum }\limits_{i=1984}^{t}\frac{\rho \left(t\right){{{{{{\mathrm{FFA}}}}}}}(t)}{T},$$
(5)

where T refers to the contemporary area of forested land48. Note that Eq. 4 and μ can be modified to account for the diversity of species-specific responses at local-to-regional scales given the acknowledgement that some species are more resilient than others and local plant water stress alters regeneration probabilities58,59. Overall, Lrf as parameterized here resulted in values approaching Lrf ~0.01 by 2050, suggesting that the inability of trees to regenerate post-fire is a minor contributor to fire-fuel feedbacks through mid-century. Modifications to the parameters in Eq. 4 resulted in only minor differences in projected FFA (Supplementary Table 3).

### Temporary fire-fuel feedbacks Lf

Most studies in forested environments show strong fire-fuel feedbacks in the first 5–10 years post-fire55,60. This temporary fire-fuel feedback, which we refer to here as Lf, tends to wane after 10 years60, with the longevity τ of the fire-fuel feedbacks varying geographically, from as short as ~15 years in warmer sites in the southwest to over ~30 years in cold mesic systems in the northern Rockies18. Herein, we use a baseline τ = 30 years, which results in a conservative estimate of future area burned.

We consider two forms for how Lf incorporates information on annual fire histories over the previous τ years: a constant feedback and a fading feedback. These forms of Lf are defined below in Eqs. 6 and 7 and plotted in Supplementary Fig. 4c.

In the case of the constant feedback, the effect of burned area on Lf remains constant over the τ years following fire. At the scale of the whole western US forested area, the constant form, therefore, assumes that the transient limitation is simply proportional to the total FFA over the preceding τ years:

$${L}_{{{{{{\mathrm{f}}}}}}}\left(t\right)=\gamma \mathop{\sum }\limits_{i=-\tau }^{-1}\frac{{{{{{{\mathrm{FFA}}}}}}}(i)}{T}.$$
(6)

In Eq. 6, parameter γ represents the strength of the feedback, described in more depth below.

The fading feedback form of Lf more heavily weights the contribution from recent FFA compared to older FFA. At the scale of the whole western US forested area, this form applies constant weight to FFA in the five most recent years given strong fire-fuel feedbacks of recent fires, and increasingly reduces the contributions from prior years based on a sinusoid function:

$${L}_{{{{{{\mathrm{f}}}}}}}\left(t\right)=\gamma \frac{\mathop{\sum }\nolimits_{i=-5}^{-1}{{{{{{\mathrm{FFA}}}}}}}\left(i\right)+\mathop{\sum }\nolimits_{i=-\tau }^{-6}{{{{{{\mathrm{FFA}}}}}}}\left(i\right)\ast \left[1-{\cos }\frac{\pi \left(-i-5\right)}{\tau -5}\right]/2}{T}.$$
(7)

Given the uncertainty in the efficacy of the fire-fuel feedback, we present results using both the constant and fading formulations for the temporary fire-fuel feedbacks.

We additionally considered three different fuel-limitation strengths γ in Eqs. 6 and 7 to account for direct and indirect potential effects of past fires: γ = 0.5, referred to as weak; γ = 1, referred to as moderate; and γ = 1.5, referred to as strong. For the weak (γ = 0.5) fuel-limitation case using the constant feedback model, the fractional forested area ineligible to burn is only half of the total area burned in the past 30 years, indicating that half of recent burned areas can reburn. For the strong-constant fuel-limitation case, the forested area ineligible to burn post-fire exceeds the total recent burned area by 50%. An example of a strong fuel limitation is a burn mosaic with reduced connectivity that constrains the ability of subsequent fire spread into the adjacent forest that did not burn in the previous τ years. We considered higher values of γ, but these yielded degraded cross-validation skills when modeling the historical period (Supplementary Table 2).

### Longevity of fire-fuel feedbacks during drought

Finally, some temporary fuel limitations can be overcome during extreme fire-weather conditions and during periods of drought. For example, while reduced fuel loads in a post-fire landscape serve as an effective barrier for fire propagation under moderate fuel aridity, the fire spread probability increases with increasing F34. Studies have found that the longevity of fire-fuel feedbacks was a third shorter during periods of extreme drought than in periods without drought stress18,34. For example, there is evidence of short-interval (<20 years) stand-replacing fires in systems with 100–300 year mean fire return intervals—suggesting that such systems can carry fire under warmer and drier fire-weather conditions20,33,61. We incorporate this effect by making the longevity parameter τ a function of contemporaneous F(t), where τ reduces linearly from 30 years toward 20 years as fuel aridity increases from 1991 to 2020 mean (F = 0) to two standard deviations above the mean (F ≥ 2):

$${\tau}={\left\{\begin{array}{c}30,\,F \, < \, 0\\ 30-5F,\,0 < F\,\le\, 2\\ 20,\,F\ge 2\end{array}\right.}.$$
(8)

The form of τ is plotted in Supplementary Fig. 4b. The resultant weighting of Lf in the fading model using the end-members of τ is displayed in Supplementary Fig. 4d.

### Running the model

Dynamic models were run over the twentieth century (1916–1983) using proximal estimates of FFA25 calibrated to the observational record62. Nominally, LANDFIRE’s gridded mean fire return interval (MFRI), an estimate of the average number of years between fires, was used to approximate a baseline FFA prior to 1916. This was used to initialize the model and serve as a reference point for projected FFA. We calculated three estimates based on the reported range for each categorical MFRI across the landscape (e.g., 11–15 years): a midpoint MFRI (e.g., 13 years), as well as the lower (e.g., 11 years) and upper bounds (e.g., 15 years) of MFRI estimates. We recognize that MFRI estimates are prone to uncertainty63, and that such estimates reflect conditions prior to European colonization which likely differ from those in the late 1800s and early 1900s28,64. However, the LANDFIRE MFRI represents the only wall-to-wall dataset of estimated fire regime parameters relevant to our study here and provide a range of likely estimates.

FFA estimates prior to the satellite era are prone to uncertainties25,65. However, initial conditions do not influence model sensitivity over the 1984–2020 period. Rather, FFA estimates serve to highlight that our formulation of L captures the increase in fuel extent in the second half of the twentieth century due to the fire deficit associated with forest management practices5,28. Finally, no significant difference in climate–fire correlations over the observational record were seen using dynamic models compared to the static models, suggesting that the influence of changes in L in recent decades has had little impact on recent fire-climate relationships—either because L has not changed significantly or that L 1 over the observational period (1984–2020). Our dynamic models suggest that suppressed L during the observational period has heightened FFA sensitivity to F.

Static and dynamic models were applied to the climate output of each CMIP6 model for the period 1950–2020 using L calculated from observations prior to 1950 and model-derived thereafter. For the 2021–2050 period, we used the observed FFA record through 2020 in calculating L and used model-derived FFA thereafter. Both the static and dynamic models implicitly include human and management effects in the regression parameters, and we assume these factors are time-invariant for future projections. Further, for each climate model run, we used a Monte-Carlo resampling procedure (n = 1000) that randomizes ε from the observed residual population therein creating 1000 replicates of modeled FFA for each climate model. Herein, we report statistics for the median of the Monte-Carlo simulations for each climate model.

In both static and dynamic models, we limit the area that can burn in a single year. The maximum FFA in the static model is defined by the estimated 100-yr return period FFA for the observational period using extreme value analysis. This works out to be 7.5% of the total forested land T—nearly four times that burned in 2020. For the dynamic models, the maximum forest that is allowed to burn in any year is 7.5% of the forested area that is eligible to burn: i.e., 7.5% of (1 − L)*T. We acknowledge that this limit is not well quantified physically but is implemented to constrain the exponential FFA–F relationships used herein. In practice, such limits occur in ~1% of model years for 2021–2050. Similar quantitative results were seen by capping F ≤ 3, which implies a saturation effect of F on FFA. Finally, while we ran the model at the aggregated scale of western US forests, the model may conceptually be run at subregional scales. We note that the strength of fire-feedbacks, climate–fire relationships, as well as model parameterizations will likely vary on subregional scales.

### Statistical information

Model cross-validation was performed to assess the skill of the models. Models using Eqs. 1 and 2 were built using training data during 1984–2000 and validated for 2001–2020. We evaluated skill by three metrics: model bias as the ratio of total modeled FFA to total observed FFA; the coefficient of efficiency (CE) as a measure of accuracy relative to a null model; and the correlation coefficient between modeled and observed log(FFA). Note that measures of bias and CE were calculated using non-log transformed data.

We assessed the statistical significance of cross-validation skill by resampling the residual term ε in Eqs. 1 and 2. This involved developing and testing 1000 iterations of the model subject to a random sampling of ε. We deem a model to have significant skill when >95% of the iterations had bias CE > 0, >95% of the iterations had r > 0, and the inner 95% of the simulations included a bias of 0.

Supplementary Table 2 shows that the static model and many of the dynamic models have significant cross-validated skills. However, skill decreased in the dynamic models as the feedback strength increases. While the weak dynamic feedback models had similar cross-validation skill as the static model, dynamic models with very strong feedbacks (γ ≥ 2) had sizeable underpredictions in FFA by up to 46% for the validation period. Hence, we excluded such parameters from the further analysis given that such results were incongruent with the observational record.

Three statistical metrics of annual variability of FFA were calculated for both static and dynamic models. First, we used generalized extreme value theory to estimate recurrence intervals for FFA greater than equal to that of the 2020 fire season. Second, we calculated the interquartile range (IQR) in modeled FFA to examine changing interannual variability. Lastly, we examined the percent of years with modeled FFA below the 1991–2020 observed median as a measure of quiescent fire years. Calculations were performed separately for each climate model for 1991–2020 and 2021–2050.

## Data availability

Observed gridded climate data sets are publicly available from the PRISM Climate Group, Oregon State University (http://prism.oregonstate.edu) and ERA-5 (https://cds.climate.copernicus.eu/), while CMIP6 (Supplementary Table 4) model output is available through the Earth System Grid Foundation (ESGF). Gridded burned area data are available through the Monitoring Trends in Burn Severity Program (http://mtbs.gov) and MODIS global burned area product MCD64A1 (https://modis-fire.umd.edu/ba.html). Summarized time series of observed annual F and FFA through 2020 as well as summarized annual modeled data from 30 different CMIP6 projections are provided on Dryad (https://datadryad.org/stash/share/yxGFk_OS2FyR8C1nBaExc9uWakmbtndhmq8xiEkoInM).

## Code availability

Software for running the various models is available at https://github.com/abatz/firemodel.

## References

1. 1.

Westerling, A. Increasing western US forest wildfire activity: sensitivity to changes in the timing of spring. Philos. Trans. R. Soc. B Biol. Sci. 371, 20150178 (2016).

2. 2.

Higuera, P. E. & Abatzoglou, J. T. Record-setting climate enabled the extraordinary 2020 fire season in the western United States. Glob. Chang. Biol. 27, 1–2 (2021).

3. 3.

Abatzoglou, J. T. & Williams, A. P. Impact of anthropogenic climate change on wildfire across western US forests. Proc. Natl. Acad. Sci. USA 113, 11770–11775 (2016).

4. 4.

North, M. P. et al. Reform forest fire management. Science 349, 1280–1281 (2015).

5. 5.

Parks, S. A. et al. Wildland fire deficit and surplus in the western United States, 1984–2012. Ecosphere 6, 1–13 (2015).

6. 6.

Hagmann, R. K. et al. Evidence for widespread changes in the structure, composition, and fire regimes of western North American forests. Ecol. Appl. https://doi.org/10.1002/eap.2431 (2021).

7. 7.

Abatzoglou, J. T., Williams, A. P., Boschetti, L., Zubkova, M. & Kolden, C. A. Global patterns of interannual climate-fire relationships. Glob. Chang. Biol. 24, 5164–5175 (2018).

8. 8.

Jolly, W. et al. Climate-induced variations in global wildfire danger from 1979 to 2013. Nat. Commun. 6, 7537 (2015).

9. 9.

Flannigan, M. et al. Global wildland fire season severity in the 21st century. For. Ecol. Manage. 294, 54–61 (2013).

10. 10.

Holden, Z. A. et al. Decreasing fire season precipitation increased recent western US forest wildfire activity. Proc. Natl. Acad. Sci. USA 115, E8349–E8357 (2018).

11. 11.

Stavros, E. N. N., Abatzoglou, J. T. J. T., McKenzie, D. & Larkin, N. K. N. K. Regional projections of the likelihood of very large wildland fires under a changing climate in the contiguous Western United States. Clim. Change 126, 455–468 (2014).

12. 12.

Brey, S. J., Barnes, E. A., Pierce, J. R., Swann, A. L. S. & Fischer, E. V. Past variance and future projections of the environmental conditions driving western U.S. summertime wildfire burn area. Earth’s Future 9, e2020EF001645 (2021).

13. 13.

Abatzoglou, J. T., Williams, A. P. & Barbero, R. Global emergence of anthropogenic climate change in fire weather indices. Geophys. Res. Lett. 46, 326–336 (2019).

14. 14.

Goss, M. et al. Climate change is increasing the risk of extreme autumn wildfire conditions across California. Environ. Res. Lett. 15, 094016(2020).

15. 15.

McKenzie, D. & Littell, J. S. Climate change and the eco-hydrology of fire: will area burned increase in a warming western U.S.? Ecol. Appl. 27, 26–36 (2017).

16. 16.

Littell, J. S., McKenzie, D., Wan, H. Y. & Cushman, S. A. Climate change and future wildfire in the western United States: an ecological approach to nonstationarity. Earth’s Future 6, 1097–1111 (2018).

17. 17.

Westerling, A. L., Turner, M. G., Smithwick, E. A. H., Romme, W. H. & Ryan, M. G. Continued warming could transform Greater Yellowstone fire regimes by mid-21st century. Proc. Natl. Acad. Sci. USA 108, 13165–13170 (2011).

18. 18.

Parks, S. A., Parisien, M., Miller, C., Holsinger, L. M. & Baggett, L. S. Fine‐scale spatial climate variation and drought mediate the likelihood of reburning. Ecol. Appl. 28, 573–586 (2018).

19. 19.

Coop, J. D. et al. Wildfire-driven forest conversion in western North American landscapes. Bioscience 70, 659–673 (2020).

20. 20.

Turner, M. G., Braziunas, K. H., Hansen, W. D. & Harvey, B. J. Short-interval severe fire erodes the resilience of subalpine lodgepole pine forests. Proc. Natl. Acad. Sci. USA 116, 11319–11328 (2019).

21. 21.

Hurteau, M. D., Liang, S., Westerling, A. L. & Wiedinmyer, C. Vegetation-fire feedback reduces projected area burned under climate change. Sci. Rep. 9, 2838 (2019).

22. 22.

Parks, S. A., Miller, C., Holsinger, L. M., Baggett, L. S. & Bird, B. J. Wildland fire limits subsequent fire occurrence. Int. J. Wildl. Fire 25, 182–190 (2016).

23. 23.

Davis, K. T. et al. Wildfires and climate change push low-elevation forests across a critical climate threshold for tree regeneration. Proc. Natl. Acad. Sci. USA 116, 6193–6198 (2019).

24. 24.

Hansen, W. D., Abendroth, D., Rammer, W., Seidl, R. & Turner, M. G. Can wildland fire management alter 21st‐century subalpine fire and forests in Grand Teton National Park, Wyoming, USA? Ecol. Appl. 30, e02030 (2020).

25. 25.

Littell, J. S., McKenzie, D., Peterson, D. L. & Westerling, A. L. Climate and wildfire area burned in western US ecoprovinces, 1916-2003. Ecol. Appl. 19, 1003–1021 (2009).

26. 26.

Williams, A. P. et al. Correlations between components of the water balance and burned area reveal new insights for predicting forest fire area in the southwest United States. Int. J. Wildl. Fire 24, 14–26 (2015).

27. 27.

Williams, A. P. et al. Observed impacts of anthropogenic climate change on wildfire in California. Earth’s Future 7, 892–910 (2019).

28. 28.

Marlon, J. R. et al. Long-term perspective on wildfires in the western USA. Proc. Natl. Acad. Sci. USA 109, E535–E543 (2012).

29. 29.

Kennedy, M. C., Bart, R. R., Tague, C. L. & Choate, J. S. Does hot and dry equal more wildfire? Contrasting short- and long-term climate effects on fire in the Sierra Nevada. CA. Ecosph. 12, e03657 (2021).

30. 30.

Berner, L. T., Law, B. E., Meddens, A. J. H. & Hicke, J. A. Tree mortality from fires, bark beetles, and timber harvest during a hot and dry decade in the western United States (2003–2012). Environ. Res. Lett. 12, 065005 (2017).

31. 31.

Donato, D. C. et al. Post-wildfire logging hinders regeneration and increases fire risk. Science 311, 352 LP–352352 (2006).

32. 32.

Hanan, E. J. et al. How climate change and fire exclusion drive wildfire regimes at actionable scales. Environ. Res. Lett. 16, 024051 (2020).

33. 33.

Harvey, B. J., Donato, D. & Turner, M. G. Burn me twice, shame on who? Interactions between successive forest fires across a temperate mountain region. Ecology 97, 2272–2282 (2016).

34. 34.

Parks, S. A., Holsinger, L. M., Miller, C. & Nelson, C. R. Wildland fire as a self-regulating mechanism: the role of previous burns and weather in limiting fire progression. Ecol. Appl. 25, 1478–1492 (2015).

35. 35.

Parks, S. A., Miller, C., Nelson, C. R. & Holden, Z. A. Previous fires moderate burn severity of subsequent wildland fires in two large western US wilderness areas. Ecosystems 17, 29–42 (2014).

36. 36.

Stewart, O. C. Forgotten Fires: Native Americans and the Transient Wilderness (University of Oklahoma Press, 2002).

37. 37.

Bowman, D. M. J. S. et al. Human exposure and sensitivity to globally extreme wildfire events. Nat. Ecol. Evol. 1, 58 (2017).

38. 38.

Stevens‐Rumann, C. S. et al. Evidence for declining forest resilience to wildfires under climate change. Ecol. Lett. 21, 243–252 (2018).

39. 39.

Schoennagel, T. et al. Adapt to more wildfire in western North American forests as climate changes. Proc. Natl. Acad. Sci. USA 114, 4582–4590 (2017).

40. 40.

Prichard, S. J. et al. Adapting western North American forests to climate change and wildfires: ten common questions. Ecol. Appl. e02433 (2021).

41. 41.

Kolden, C. A. We’re not doing enough prescribed fire in the Western United States to mitigate wildfire risk. Fire 2, 30 (2019).

42. 42.

Kolden, C. Wildfires: count lives and homes, not hectares burnt. Nature 586, 9 (2020).

43. 43.

Hessburg, P. F., Prichard, S. J., Hagmann, R. K., Povak, N. A. & Lake, F. K. Wildfire and climate change adaptation of western North American forests: a case for intentional management. Ecol. Appl. https://doi.org/10.1002/eap.2432 (2021).

44. 44.

Daly, C. et al. Physiographically sensitive mapping of climatological temperature and precipitation across the conterminous United States. Int. J. Climatol. 28, 2031–2064 (2008).

45. 45.

Hersbach, H. et al. The ERA5 global reanalysis. Q. J. R. Meteorol. Soc. 146, 1999–2049 (2020).

46. 46.

Stephenson, N. Actual evapotranspiration and deficit: biologically meaningful correlates of vegetation distribution across spatial scales. J. Biogeogr. 25, 855–870 (1998).

47. 47.

Yang, Y., Roderick, M. L., Zhang, S., McVicar, T. R. & Donohue, R. J. Hydrologic implications of vegetation response to elevated CO2 in climate projections. Nat. Clim. Chang. 9, 44–48 (2019).

48. 48.

Rollins, M. G. LANDFIRE: a nationally consistent vegetation, wildland fire, and fuel assessment. Int. J. Wildl. Fire 18, 235–249 (2009).

49. 49.

Li, H., Sheffield, J. & Wood, E. F. Bias correction of monthly precipitation and temperature fields from Intergovernmental Panel on Climate Change AR4 models using equidistant quantile matching. J. Geophys. Res. Atmos. 115, D10101 https://doi.org/10.1029/2009JD012882 (2010).

50. 50.

Eidenshink, J. C. et al. A project for monitoring trends in burn severity. Fire Ecol. 3, 3–21 (2007).

51. 51.

Giglio, L., Boschetti, L., Roy, D. P., Humber, M. L. & Justice, C. O. The Collection 6 MODIS burned area mapping algorithm and product. Remote Sens. Environ. 217, 72–85 (2018).

52. 52.

Short, K. A spatial database of wildfires in the United States, 1992-2011. Earth Syst. Sci. Data 6, 1–27 (2014).

53. 53.

Kolden, C. A., Smith, A. M. S. & Abatzoglou, J. T. Limitations and utilisation of Monitoring Trends in Burn Severity products for assessing wildfire severity in the USA. Int. J. Wildl. Fire 24, 1023–1028 (2015).

54. 54.

Abatzoglou, J. T., Juang, C. S., Williams, A. P., Kolden, C. A. & LeRoy Westerling, A. Increasing synchronous fire danger in forests of the western United States. Geophys. Res. Lett. 48, e2020GL091377 (2020).

55. 55.

Prichard, S. J., Stevens-Rumann, C. S. & Hessburg, P. F. Tamm review: shifting global fire regimes: lessons from reburns and research needs. For. Ecol. Manage. 396, 217–233 (2017).

56. 56.

Davis, K. T. et al. Fire-catalyzed vegetation shifts in ponderosa pine and Douglas-fir forests of the western United States. Environ. Res. Lett. 15, 1040b8 (2020).

57. 57.

Littlefield, C. E., Dobrowski, S. Z., Abatzoglou, J. T., Parks, S. A. & Davis, K. T. A climatic dipole drives short-and long-term patterns of postfire forest recovery in the western United States. Proc. Natl. Acad. Sci. USA 117, 29730–29737 (2020).

58. 58.

Hansen, W. D., Braziunas, K. H., Rammer, W., Seidl, R. & Turner, M. G. It takes a few to tango: changing climate and fire regimes can cause regeneration failure of two subalpine conifers. Ecology 99, 966–977 (2018).

59. 59.

Stevens-Rumann, C. S. & Morgan, P. Tree regeneration following wildfires in the western US: a review. Fire Ecol. 15, 15 (2019).

60. 60.

Ager, A. A. et al. Effects of accelerated wildfire on future fire regimes and implications for the United States federal fire policy. Ecol. Soc. 22, 12–28 (2017).

61. 61.

Nelson, K. N., Turner, M. G., Romme, W. H. & Tinker, D. B. Simulated fire behaviour in young, postfire lodgepole pine forests. Int. J. Wildl. Fire 26, 852–865 (2017).

62. 62.

Bowman, D. M. J. S. et al. Vegetation fires in the anthropocene. Nat. Rev. Earth Environ. 1, 500–515 (2020).

63. 63.

Van de Water, K. M. & Safford, H. D. A summary of fire frequency estimates for California vegetation before Euro-American settlement. Fire Ecol. 7, 26–58 (2011).

64. 64.

Savage, M. & Swetnam, T. W. Early 19th-century fire decline following sheep pasturing in a Navajo ponderosa pine forest. Ecology 71, 2374–2378 (1990).

65. 65.

Short, K. C. Sources and implications of bias and uncertainty in a century of US wildfire activity data. Int. J. Wildl. Fire 24, 883–891 (2015).

## Author information

Authors

### Contributions

Specific contributions by authors include conceptualization: J.T.A. and D.S.B.; methodology: J.T.A., D.S.B., A.P.W., and W.D.H.; investigation: J.T.A., D.S.B., A.P.W., W.D.H., B.J.H., and C.A.K.; visualization: J.T.A.; writing—original draft: J.T.A. and D.S.B.; writing—review and editing: J.T.A., D.S.B., A.P.W., W.D.H., B.J.H., and C.A.K..

### Corresponding author

Correspondence to John T. Abatzoglou.

## Ethics declarations

### Competing interests

The authors declare no competing interests.

Peer review information Communications Earth & Environment thanks Luke Collins and the other, anonymous, reviewer(s) for their contribution to the peer review of this work. Primary Handling Editor: Clare Davis.

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Rights and permissions

Reprints and Permissions

Abatzoglou, J.T., Battisti, D.S., Williams, A.P. et al. Projected increases in western US forest fire despite growing fuel constraints. Commun Earth Environ 2, 227 (2021). https://doi.org/10.1038/s43247-021-00299-0

• Accepted:

• Published:

• DOI: https://doi.org/10.1038/s43247-021-00299-0

• ### Earth, fuel and fire

• Clare Davis

Nature Reviews Earth & Environment (2021)


text:
# Laughlin's topological argument

I have a confusion about understanding the Laughlin's topological argument on Hall conductivity quantization.

This argument states that the Hall conductivity is $$\sigma_{xy}=\frac{e}{h}Q,$$ where $Q$ is a charge transferred from the left reservoir $A$ to the right reservoir $B$ when one quantum of magnetic flux $\Phi=\Phi_0$ is inserted through the cylinder. Then it is usually told that during the flux insertion some filled states become empty and some empty states become filled. Hence $Q=en$ with $n$ being an integer number of transferred electrons so $\sigma_{xy}=(e^2/h)n$ is quantized.

I don't understand: what exactly happens with extended and localized states during the flux insertion? As known, highly degenerate Landau levels break up in the presence of disorder into extended and localized states.

What happens when the magnetic flux is inserted? As known,

1) the localized states are not affected by the flux $\Phi$ since their wave functions don't enclose the cylinder and undergo only a gauge transformation;

2) the extended states change with $\Phi$ but return to their initial form when $\Phi=\Phi_0$;

3) since a disordered system is usually a chaotic one, its energy levels don't cross (energy level repulsion);

4) since the flux is inserted adiabatically slowly, all transitions between different single-particle levels are forbidden thus all filled states remain filled and all empty states remain empty;

5) the Fermi level is placed inside the mobility gap, where only localized states exist.

With taking into account these arguments, evolution of energy levels with $\Phi$ changing from $0$ to $\Phi_0$ should look like that in the picture below.

As seen, in this picture the fillings of single-particle states don't change. So how it can happen that some integer number of electrons get transferred from localized states of the left reservoir to other localized states of the right reservoir?

• Doesn't the DOS change under the addition of flux quanta, namely the lines get scrunched up closer to the origin? – Aaron Oct 5 '17 at 15:21
• @Aaron It is interesting scenario, when extended states move from one Landau level to another (diagonal motion of red lines in the picture), I thought about it. But, in this case they should cross localized energy levels (blue lines), which separate different Landau levels. Since the crossing is forbidden, we should have some anticrossings instead... – Alexey Sokolik Oct 5 '17 at 15:30
• Why is there no diagonal motion of localized states as well? – Aaron Oct 5 '17 at 16:23
• @Aaron Because localized states are not affected by the flux at all (except unobservable gauge transformation), they do not undergo the Aaronov-Bohm effect since their wave functions does not enclose the flux. The same refers to electron states in the both reservoirs, so I don't understand how one of them can be filled and other emptied. – Alexey Sokolik Oct 5 '17 at 17:20

format: plain


text:
# How do you simplify  sqrt ((2x)/(9x))?

Apr 30, 2016

$\sqrt{\frac{2 x}{9 x}} = \frac{\sqrt{2}}{3}$ excluding $x = 0$

#### Explanation:

For any positive Real numbers $a , b$:

$\sqrt{\frac{a}{b}} = \frac{\sqrt{a}}{\sqrt{b}}$

So we find:

$\sqrt{\frac{2 \textcolor{red}{\cancel{\textcolor{b l a c k}{x}}}}{9 \textcolor{red}{\cancel{\textcolor{b l a c k}{x}}}}} = \sqrt{\frac{2}{3} ^ 2} = \frac{\sqrt{2}}{\sqrt{{3}^{2}}} = \frac{\sqrt{2}}{3}$

excluding $x = 0$, when $\sqrt{\frac{2 x}{9 x}} = \sqrt{\frac{0}{0}}$ is undefined.


text:
# American Institute of Mathematical Sciences

January  2015, 35(1): 367-397. doi: 10.3934/dcds.2015.35.367

## Symplectic groupoids and discrete constrained Lagrangian mechanics

 1 Unidad Asociada ULL-CSIC "Geometría Diferencial y Mecánica Geométrica", Departamento de Matemática Fundamental, Facultad de Matemáticas, Universidad de la Laguna, La Laguna, Tenerife, Canary Islands, Spain 2 Instituto de Ciencias Matemáticas, CSIC-UAM-UC3M-UCM, Campus de Cantoblanco, UAM, C/Nicolás Cabrera, 15, 28049 Madrid 3 Department of Mathematics, Washington University in St. Louis, Campus Box 1146, One Brookings Drive, St. Louis, Missouri 63130-4899, United States

Received  April 2013 Revised  July 2014 Published  August 2014

In this article, we generalize the theory of discrete Lagrangian mechanics and variational integrators in two principal directions. First, we show that Lagrangian submanifolds of symplectic groupoids give rise to discrete dynamical systems, and we study the properties of these systems, including their regularity and reversibility, from the perspective of symplectic and Poisson geometry. Next, we use this framework---along with a generalized notion of generating function due to Śniatycki and Tulczyjew [18]---to develop a theory of discrete constrained Lagrangian mechanics. This allows for systems with arbitrary constraints, including those which are non-integrable (in an appropriate discrete, variational sense). In addition to characterizing the dynamics of these constrained systems, we also develop a theory of reduction and Noether symmetries, and study the relationship between the dynamics and variational principles. Finally, we apply this theory to discretize several concrete examples of constrained systems in mechanics and optimal control.
Citation: Juan Carlos Marrero, David Martín de Diego, Ari Stern. Symplectic groupoids and discrete constrained Lagrangian mechanics. Discrete & Continuous Dynamical Systems - A, 2015, 35 (1) : 367-397. doi: 10.3934/dcds.2015.35.367
##### References:
 [1] R. Abraham, J. E. Marsden and T. Ratiu, Manifolds, Tensor Analysis, and Applications,, 2nd edition, (1988). doi: 10.1007/978-1-4612-1029-0. [2] N. Bou-Rabee and J. E. Marsden, Hamilton-Pontryagin integrators on Lie groups part I: Introduction and structure-preserving properties,, Found. Comput. Math., 9 (2009), 197. doi: 10.1007/s10208-008-9030-4. [3] A. Cannas da Silva and A. Weinstein, Geometric Models for Noncommutative Algebras,, Berkeley Mathematics Lecture Notes, (1999). [4] A. Coste, P. Dazord and A. Weinstein, Groupoï des symplectiques,, in Publications du Département de Mathématiques. Nouvelle Série. A, (1987), 1. [5] Z. Ge, Generating functions, Hamilton-Jacobi equations and symplectic groupoids on Poisson manifolds,, Indiana Univ. Math. J., 39 (1990), 859. doi: 10.1512/iumj.1990.39.39042. [6] E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations,, 2nd edition, (2006). [7] D. Iglesias, J. C. Marrero, D. Martín de Diego and D. Sosa, Singular Lagrangian systems and variational constrained mechanics on Lie algebroids,, Dyn. Syst., 23 (2008), 351. doi: 10.1080/14689360802294220. [8] C. Kane, J. E. Marsden and M. Ortiz, Symplectic-energy-momentum preserving variational integrators,, J. Math. Phys., 40 (1999), 3353. doi: 10.1063/1.532892. [9] W.-S. Koon and J. E. Marsden, Optimal control for holonomic and nonholonomic mechanical systems with symmetry and Lagrangian reduction,, SIAM J. Control Optim., 35 (1997), 901. doi: 10.1137/S0363012995290367. [10] P. Libermann and C.-M. Marle, Symplectic Geometry and Analytical Mechanics,, Translated from the French by Bertram Eugene Schwarzbach, (1987). [11] K. C. H. Mackenzie, General Theory of Lie Groupoids and Lie Algebroids,, London Mathematical Society Lecture Note Series, (2005). doi: 10.1017/CBO9781107325883. [12] C.-M. Marle, From momentum maps and dual pairs to symplectic and Poisson groupoids,, in The Breadth of Symplectic and Poisson Geometry, (2005), 493. doi: 10.1007/0-8176-4419-9\_17. [13] J. C. Marrero, D. Martín de Diego and E. Martínez, Discrete Lagrangian and Hamiltonian mechanics on Lie groupoids,, Nonlinearity, 19 (2006), 1313. doi: 10.1088/0951-7715/19/6/006. [14] J. C. Marrero, D. Martín de Diego and E. Martínez, The exact discrete Lagrangian function on Lie groupoids and some applications,, in preparation., (). [15] J. E. Marsden and M. West, Discrete mechanics and variational integrators,, Acta Numer., 10 (2001), 357. doi: 10.1017/S096249290100006X. [16] R. I. McLachlan and C. Scovel, A survey of open problems in symplectic integration,, in Integration Algorithms and Classical Mechanics (Toronto, (1993), 151. [17] J. Moser and A. P. Veselov, Discrete versions of some classical integrable systems and factorization of matrix polynomials,, Comm. Math. Phys., 139 (1991), 217. doi: 10.1007/BF02352494. [18] J. Śniatycki and W. M. Tulczyjew, Generating forms of Lagrangian submanifolds,, Indiana Univ. Math. J., 22 (1972), 267. doi: 10.1512/iumj.1973.22.22021. [19] A. Stern, Discrete Hamilton-Pontryagin mechanics and generating functions on Lie groupoids,, J. Symplectic Geom., 8 (2010), 225. doi: 10.4310/JSG.2010.v8.n2.a5. [20] Y. B. Suris, Hamiltonian methods of Runge-Kutta type and their variational interpretation,, Mat. Model., 2 (1990), 78. [21] W. M. Tulczyjew, The Legendre transformation,, Ann. Inst. H. Poincaré Sect. A (N.S.), 27 (1977), 101. [22] A. Weinstein, Coisotropic calculus and Poisson groupoids,, J. Math. Soc. Japan, 40 (1988), 705. doi: 10.2969/jmsj/04040705. [23] A. Weinstein, Lagrangian mechanics and groupoids,, in Mechanics Day (Waterloo, (1992), 207. [24] P. Xu, On Poisson groupoids,, Internat. J. Math., 6 (1995), 101. doi: 10.1142/S0129167X95000080. [25] H. Yoshimura and J. E. Marsden, Dirac structures in Lagrangian mechanics. II. Variational structures,, J. Geom. Phys., 57 (2006), 209. doi: 10.1016/j.geomphys.2006.02.012.

show all references

##### References:
 [1] R. Abraham, J. E. Marsden and T. Ratiu, Manifolds, Tensor Analysis, and Applications,, 2nd edition, (1988). doi: 10.1007/978-1-4612-1029-0. [2] N. Bou-Rabee and J. E. Marsden, Hamilton-Pontryagin integrators on Lie groups part I: Introduction and structure-preserving properties,, Found. Comput. Math., 9 (2009), 197. doi: 10.1007/s10208-008-9030-4. [3] A. Cannas da Silva and A. Weinstein, Geometric Models for Noncommutative Algebras,, Berkeley Mathematics Lecture Notes, (1999). [4] A. Coste, P. Dazord and A. Weinstein, Groupoï des symplectiques,, in Publications du Département de Mathématiques. Nouvelle Série. A, (1987), 1. [5] Z. Ge, Generating functions, Hamilton-Jacobi equations and symplectic groupoids on Poisson manifolds,, Indiana Univ. Math. J., 39 (1990), 859. doi: 10.1512/iumj.1990.39.39042. [6] E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations,, 2nd edition, (2006). [7] D. Iglesias, J. C. Marrero, D. Martín de Diego and D. Sosa, Singular Lagrangian systems and variational constrained mechanics on Lie algebroids,, Dyn. Syst., 23 (2008), 351. doi: 10.1080/14689360802294220. [8] C. Kane, J. E. Marsden and M. Ortiz, Symplectic-energy-momentum preserving variational integrators,, J. Math. Phys., 40 (1999), 3353. doi: 10.1063/1.532892. [9] W.-S. Koon and J. E. Marsden, Optimal control for holonomic and nonholonomic mechanical systems with symmetry and Lagrangian reduction,, SIAM J. Control Optim., 35 (1997), 901. doi: 10.1137/S0363012995290367. [10] P. Libermann and C.-M. Marle, Symplectic Geometry and Analytical Mechanics,, Translated from the French by Bertram Eugene Schwarzbach, (1987). [11] K. C. H. Mackenzie, General Theory of Lie Groupoids and Lie Algebroids,, London Mathematical Society Lecture Note Series, (2005). doi: 10.1017/CBO9781107325883. [12] C.-M. Marle, From momentum maps and dual pairs to symplectic and Poisson groupoids,, in The Breadth of Symplectic and Poisson Geometry, (2005), 493. doi: 10.1007/0-8176-4419-9\_17. [13] J. C. Marrero, D. Martín de Diego and E. Martínez, Discrete Lagrangian and Hamiltonian mechanics on Lie groupoids,, Nonlinearity, 19 (2006), 1313. doi: 10.1088/0951-7715/19/6/006. [14] J. C. Marrero, D. Martín de Diego and E. Martínez, The exact discrete Lagrangian function on Lie groupoids and some applications,, in preparation., (). [15] J. E. Marsden and M. West, Discrete mechanics and variational integrators,, Acta Numer., 10 (2001), 357. doi: 10.1017/S096249290100006X. [16] R. I. McLachlan and C. Scovel, A survey of open problems in symplectic integration,, in Integration Algorithms and Classical Mechanics (Toronto, (1993), 151. [17] J. Moser and A. P. Veselov, Discrete versions of some classical integrable systems and factorization of matrix polynomials,, Comm. Math. Phys., 139 (1991), 217. doi: 10.1007/BF02352494. [18] J. Śniatycki and W. M. Tulczyjew, Generating forms of Lagrangian submanifolds,, Indiana Univ. Math. J., 22 (1972), 267. doi: 10.1512/iumj.1973.22.22021. [19] A. Stern, Discrete Hamilton-Pontryagin mechanics and generating functions on Lie groupoids,, J. Symplectic Geom., 8 (2010), 225. doi: 10.4310/JSG.2010.v8.n2.a5. [20] Y. B. Suris, Hamiltonian methods of Runge-Kutta type and their variational interpretation,, Mat. Model., 2 (1990), 78. [21] W. M. Tulczyjew, The Legendre transformation,, Ann. Inst. H. Poincaré Sect. A (N.S.), 27 (1977), 101. [22] A. Weinstein, Coisotropic calculus and Poisson groupoids,, J. Math. Soc. Japan, 40 (1988), 705. doi: 10.2969/jmsj/04040705. [23] A. Weinstein, Lagrangian mechanics and groupoids,, in Mechanics Day (Waterloo, (1992), 207. [24] P. Xu, On Poisson groupoids,, Internat. J. Math., 6 (1995), 101. doi: 10.1142/S0129167X95000080. [25] H. Yoshimura and J. E. Marsden, Dirac structures in Lagrangian mechanics. II. Variational structures,, J. Geom. Phys., 57 (2006), 209. doi: 10.1016/j.geomphys.2006.02.012.
 [1] Melvin Leok, Diana Sosa. Dirac structures and Hamilton-Jacobi theory for Lagrangian mechanics on Lie algebroids. Journal of Geometric Mechanics, 2012, 4 (4) : 421-442. doi: 10.3934/jgm.2012.4.421 [2] Jorge Cortés, Manuel de León, Juan Carlos Marrero, Eduardo Martínez. Nonholonomic Lagrangian systems on Lie algebroids. Discrete & Continuous Dynamical Systems - A, 2009, 24 (2) : 213-271. doi: 10.3934/dcds.2009.24.213 [3] Santiago Cañez. Double groupoids and the symplectic category. Journal of Geometric Mechanics, 2018, 10 (2) : 217-250. doi: 10.3934/jgm.2018009 [4] Leonardo Colombo, David Martín de Diego. Second-order variational problems on Lie groupoids and optimal control applications. Discrete & Continuous Dynamical Systems - A, 2016, 36 (11) : 6023-6064. doi: 10.3934/dcds.2016064 [5] Marie-Claude Arnaud. When are the invariant submanifolds of symplectic dynamics Lagrangian?. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 1811-1827. doi: 10.3934/dcds.2014.34.1811 [6] Gennadi Sardanashvily. Lagrangian dynamics of submanifolds. Relativistic mechanics. Journal of Geometric Mechanics, 2012, 4 (1) : 99-110. doi: 10.3934/jgm.2012.4.99 [7] Dennise García-Beltrán, José A. Vallejo, Yurii Vorobiev. Lie algebroids generated by cohomology operators. Journal of Geometric Mechanics, 2015, 7 (3) : 295-315. doi: 10.3934/jgm.2015.7.295 [8] Lijin Wang, Jialin Hong. Generating functions for stochastic symplectic methods. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 1211-1228. doi: 10.3934/dcds.2014.34.1211 [9] Juan Carlos Marrero, D. Martín de Diego, Diana Sosa. Variational constrained mechanics on Lie affgebroids. Discrete & Continuous Dynamical Systems - S, 2010, 3 (1) : 105-128. doi: 10.3934/dcdss.2010.3.105 [10] Katarzyna Grabowska, Marcin Zając. The Tulczyjew triple in mechanics on a Lie group. Journal of Geometric Mechanics, 2016, 8 (4) : 413-435. doi: 10.3934/jgm.2016014 [11] K. C. H. Mackenzie. Drinfel'd doubles and Ehresmann doubles for Lie algebroids and Lie bialgebroids. Electronic Research Announcements, 1998, 4: 74-87. [12] Eduardo Martínez. Classical field theory on Lie algebroids: Multisymplectic formalism. Journal of Geometric Mechanics, 2018, 10 (1) : 93-138. doi: 10.3934/jgm.2018004 [13] Eduardo Martínez. Higher-order variational calculus on Lie algebroids. Journal of Geometric Mechanics, 2015, 7 (1) : 81-108. doi: 10.3934/jgm.2015.7.81 [14] Cédric M. Campos, Elisa Guzmán, Juan Carlos Marrero. Classical field theories of first order and Lagrangian submanifolds of premultisymplectic manifolds. Journal of Geometric Mechanics, 2012, 4 (1) : 1-26. doi: 10.3934/jgm.2012.4.1 [15] Henry O. Jacobs, Hiroaki Yoshimura. Tensor products of Dirac structures and interconnection in Lagrangian mechanics. Journal of Geometric Mechanics, 2014, 6 (1) : 67-98. doi: 10.3934/jgm.2014.6.67 [16] Marco Zambon, Chenchang Zhu. Distributions and quotients on degree $1$ NQ-manifolds and Lie algebroids. Journal of Geometric Mechanics, 2012, 4 (4) : 469-485. doi: 10.3934/jgm.2012.4.469 [17] José F. Cariñena, Irina Gheorghiu, Eduardo Martínez. Jacobi fields for second-order differential equations on Lie algebroids. Conference Publications, 2015, 2015 (special) : 213-222. doi: 10.3934/proc.2015.0213 [18] Juan Carlos Marrero. Hamiltonian mechanical systems on Lie algebroids, unimodularity and preservation of volumes. Journal of Geometric Mechanics, 2010, 2 (3) : 243-263. doi: 10.3934/jgm.2010.2.243 [19] Sergio Grillo, Marcela Zuccalli. Variational reduction of Lagrangian systems with general constraints. Journal of Geometric Mechanics, 2012, 4 (1) : 49-88. doi: 10.3934/jgm.2012.4.49 [20] Robert Lauter and Victor Nistor. On spectra of geometric operators on open manifolds and differentiable groupoids. Electronic Research Announcements, 2001, 7: 45-53.

2017 Impact Factor: 1.179


text:
### Theory:

Rule 1: A variable is assigned to the value not known or to be found.

Let the number of apples that the boy initially had $$= x$$.

Rule 2: Then, the expressions can be formed in by the conditions specified in the question.

Number of apples given to sister $$= 3$$.

Number of apples left for the boy $$= 2$$.

Number of apples he had initially $$–$$ Number of apples given to the girl $$=$$ Number of apples the boy is left with.

Rule 3: The expressions are finally equated with the values given in the question.
Number of apples the boy left with:

$$x - 3 =2$$.

Thus, the equation set up is $$x-3 = 2$$.


text:
# standard error for difference in prediction using R

I want to calculate standard error for difference between two predictions, but have little idea.

pred <- predict(hsg_prob, newdata=data.frame("three_kids" = 1,
"post_arra" = c(0,1),
"three_x_arra" = c(0,1)),
se.fit = TRUE,
type = "response")

pred

This gives me

$fit 1 2 0.7469388 0.7578797$se.fit
1          2
0.01388808 0.01621392

$residual.scale [1] 1  What I am interested in is the standard error of pred$fit[2]-pred\$fit[1], which is the standard error of these two predictions 0.7578797 - 0.7469388

I also tried using diff(pred), but it doesn't come out with a standard error.

Is there any easy way to calculate standard error for this?

Thanks!

• It depends on the model: what kind of object is hsg_prob? – whuber Mar 23 '20 at 21:46
• @whuber hsg_prob is a probit model. This is to examine if the tax credit policy adoption increases the labor force participation (LFP) of the treatment group. Basically the difference is therefore LFP of the treatment group minus that of the control group. I want to have the standard error of that difference! – Girim Ban Mar 23 '20 at 23:20
• Please explain that by editing your post. – whuber Mar 24 '20 at 14:05


text:
## Mathematicians Of The Day

### 13th October

#### Quotation of the day

##### From Nicolas Malebranche
Just as our eyes need light in order to see, our minds need ideas in order to conceive.


text:
## Si3N4 - Ceramic Si3N4 layer

### Connection Diagram:

 LEFT RIGHT

 Connections(2) Position Remark RIGHT Right LEFT Left Thermal node

 Parameters(5) Default Remark ThermalCapacity[W/m3K] 0.1e6 Specific Thermal Capacity in [Watt / m*m*m Kelvin] ThermalConductivity[W/mK] 70 Specific Thermal Conductivity in [Watt / meter Kelvin] InitialTemperature[Celcius] 25 Initial temperature of the heat sink Thickness[m] 1m Thickness of the layer [ m] Area[m*m] 1e-4 Surface area [m * m]

 Function Layer from Ceramic Si3N4. The heat is transfered in the direction of the thickness of the material. Special Depending on the temperature the heat sink is colored, where the color level is defined by the voltage level in the animation properties dialog box. Note Specify the initial temperature.

 Status Standard

 Select from Components\Library\Thermal\Layer\Ceramic


text:
# source:docs/Working/re/re-main.tex@3458

Last change on this file since 3458 was 3458, checked in by lindanl, 6 years ago

File size: 14.4 KB
Line
1\documentclass[a4paper,10pt]{article}
2\usepackage[utf8]{inputenc}
3\usepackage{graphicx}
4
5%opening
6\title{Fast Regular Expression Matching with Bit-parallel Data Streams}
7\author{
8{Robert D. Cameron} \\
9\and
10{Kenneth S. Herdy} \\
11\and
12{Ben Hull} \\
13\and
14{Thomas C. Shermer} \\
15\\School of Computing Science
16\\Simon Fraser University
17}
18\begin{document}
19
20\date{}
21\maketitle
22
23\begin{abstract}
24
25A parallel regular expression matching pattern method is introduced and compared
26with existing approaches for efficient on-line search.
27The method is based on the concept of bit-parallel data streams,
28in which parallel streams of bits are formed such
29that each stream comprises bits in one-to-one correspondence with the
30character code units of a source data stream.
31
32An implementation of the techniques in the form of a regular expression
33compiler is discussed. The compiler accepts a regular expression and
34forms unbounded bit-parallel data stream statements. Bit-parallel operations
35are then transformed into a low-level C-based implementation for compilation into native
36pattern matching application code. These low-level C-based implementations take advantage of
37the SIMD (single-instruction multiple-data) capabilities of commodity
38processors to yield a dramatic speed-up over traditional byte-at-a-time approaches.
39On processors supporting W-bit addition operations, the method processes W source characters
40in parallel and performs up to W finite state transitions per clock cycle.
41We further improve our methods through the introduce a new bit-parallel scanning primitive, {\em Match Star}.
42which performs a parallel Kleene closure operation over character classes
43and without backtracking. % expand and rephrase description of Match Star
44
45We evaluate the performance of our method in comparison with several widely known {\em grep}
46implemenations, {\em Gnu grep}, {\em agrep}, {\em nr-grep}.
47Performance results are analyzed using the performance monitoring counters
48of commodity hardware. Overall, our results demonstrate dramatic speed-ups
49over other publically available software.
50
51\end{abstract}
52
53\section{Introduction}
54\label{Introduction}
55%\input{introduction.tex}
56
57Regular expresssion matching is an extensively studied problem with application to
58various problem domains, for example, text-processing and bioinformatics. A multitude of algorithms
59and software tools exist to address the specific demands of the various problem domains. % reword
60
61The pattern matching problem can be
62stated as follows. Given a text T$_{1..n}$ of n characters and a pattern P,
63find all the text positions of T that start an occurrence of P. Alternatively,
64one may want all the final positions of occurrences. Some applications require
65slightly different output such as the line that matches the pattern.
66
67A pattern P can be a simple string, but it can also be a regular expression.
68A regular expression, is an expression that specifies a set of strings
69and is composed of (i) simple strings and (ii) the
70union, concatenation and Kleene closure of other regular expressions.
71To avoid parentheses it is assumed that the Kleene star has the highest priority,
72next concatenation and then alternation, however, most formalisms provides grouping
73operators to allow the definition of scope and operator precedence.
74Readers unfamiliar with the concept of regular expression matching are referred
75classical texts such as \cite{aho2007}.
76
77Regular expression matching is typically performed using a wide variety of
78publically available software tools designed for efficient on-line pattern matching.
79For example, UNIX grep, Gnu grep, agrep, cgrep, nr-grep, and Perl regular
80expressions \cite{abou-assaleh2004}. Amongst these tools Gnu grep (egrep),
81agrep, and nr-grep are widely considered the fastest regular expression
82matching tools in practice \cite{navarro2000}.
83
84% source: Parallel Scanning with BitStream Addition: An XML Case Study
85Although traditional finite state machine methods used in the scanning and parsing of
86text streams is considered to be the hardest of the â13 dwarvesâ to parallelize
87[1], bit-parallel data stream technology shows considerable promise as a general
88approach to regular expression matching. In this approach, character
89streams are processed W positions at a time using the W-bit SIMD registers
90commonly found on commodity processors (e.g., 128-bit XMM registers on Intel/AMD chips).
91This is achieved by first slicing the byte streams into eight separate basis bitstreams, one for each bit
92position within the byte. These basis bitstreams are then combined with bitwise
93logic and shifting operations to compute further parallel bit streams of interest.
94
95We further increase the performance of our approach with the introduction of a new parallel
96scanning primitive coined {\em Match Star}. % expand and reword desc. of Match Star
97
98The remainder of this paper is organized as follows.
99Section~\ref{Basic Concepts} introduces the notations and basic concepts used throughout this paper.
100Section~\ref{Background} presents background material on classical automata-based approaches
101to regular expression matching and describes the {\em grep} family utilities.
102Next, section~\ref{Bit-parallel Data Streams} describes our parallel regular expression matching techniques.
103Section~\ref{Compiler Technology} presents our software toolchain for constructing pattern matching applications.
104Section~\ref{Methodology} describes the evaluation framework and Section~\ref{Experimental Results}
105presents a detailed performance analysis of our data parallel bitstream techniques in comparison to
106several software tools. Section~\ref{Conclusion} concludes the paper.
107
108The fundamental contribution of this paper is fully general approach to regular expression matching
109using bit-parallel data stream operations. The algorithmic aspects of this paper build upon
110the fundamental concepts of our previous work \cite{cameron2008high, cameron2009parallel, cameron2011parallel, lin2012parabix}.
111Specific contributions include:
112\begin{itemize}
113\item compilation of regular expressions into unbounded bit-parallel data stream equations;
114\item documentation of character classes compilation into bit-parallel character class data streams;
115\item Match Star parallel scanning primitive;
116\item efficient support for unicode characters.
117\end{itemize}
118
119\section{Basic Concepts}
120\label{Basic Concepts}
121In this section, we define the notation and basic concepts used throughout this paper.
122
123\subsection{Notation}
124We use the following notations. Let $P=p_{1}p_{2}\ldots{}p_{m}$
125be a pattern of length m and $T=t_{1}t_{2}\ldots{}t_{n}$
126be a text of length n both defined over a finite alphabet $sigma$ of size $alpha$.
127The goal of simple pattern expression matching is to find all the text positions of T that follow
128an occurrence of P. P may be a simple pattern, extended pattern, or a regular expression.
129
130We use C notations to represent bitwise operations $\lnot{}$, $\lor{}$, $\land{}$, $\oplus{}$
131represent bitwise NOT, OR, AND, XOR, respectively. Operators $\ll{}k$, and $\gg{}$ represent
132logical left shift, and logical right shift, respectively and are further modulated by
133the number of bit positions a given value shall be shifted by, for example shift left by n''.
134Vacant bit-positions are filled in with zeroes.
135
136\subsection{Regular Expressions}
137
138% Define regular expressions (a recursive def), character classes, bounded repetition
139
140\section{Background}
141\label{Background}
142%\input{background.tex}
143
144\subsection{Regular Expressions and Finite Automata}
145
146The origins of regular expression matching date back to automata theory
147and formal language theory developed by Kleene in the 1950s \cite{kleene1951}.
148Thompson \cite{thompson1968} is credited with the first construction to convert regular expressions
149to nondeterministic finite automata (NFA) for regular expression matching.
150Following Thompson's approach, a regular expression of length m is first converted
151to an NFA with O(m) nodes. It is possible to search a text of length n using the
152NFA directly in O(mn) worst case time. Often, a more efficient choice
153is to convert the NFA into a DFA. A DFA has only a single active state and
154allows to search the text at O(n) worst-case optimal. It is well known that the
155conversion of the NFA to the DFA may result in the state explosion problem.
156That is the resultant DFA may have O($2^m$) states.
157
158Thompson's original work marked the beginning of a long line of
159regular expression pattern matching methods that
160process an input string, character-at-a-time,
161and that transition from state to state
162according to the current state and the next input character.
163
165O(n) worst-case optimal efficiency, simple string matching algorithms,
166such as the Boyer-Moore family of algorithms, skip input characters
167to achieve sublinear times in the average case \cite{boyer1977fast}.
168
169Boyer-Moore methods, begin comparison from the end of the pattern instead of the
170beginning and precompute skip information
171to determine how far ahead a pattern search can skip in the input whenever
172a non-matching character is encountered. Generally, Boyer-Moore family
173algorithms improve faster as the pattern being searched for becomes longer.
174In many cases, the techniques used to skip characters in simple string matching
175approaches can be extended to regular expression matching.
176Widely known techniques used to facilitate character skipping in regular
177expression matching include necessary strings and backward suffix matching
178inspired by the Backward Dawg Matching (BDM) algorithm \cite{Navarro02patternmatching}.
179
180\subsection{Bit-parallel Simulation of Automata}
181
182bit-parallelism \cite{Baeza-yates_anew}
183
184Shift-Or / Shift-And \cite{wu1992fast}
185
186Bit-parallel suffix automata (Backward Non-Deterministic Dawg Matching (BNDM) \cite{navarro1998bit} algorithm)
187
188i.e. bit parallel simulation of automata
189
190\subsection{Software Tools} % Methodology section?
191
192%This subsection relates the performance of well known tools (Gnu grep, agrep, nr-grep)
193%to the above pattern matching algorithms.
194
195%Source: http://pages.cs.wisc.edu/~mdant/cs520_4.html
196
197%Thompson created the first grep (UNIX grep) as a standalone adaptation
198%of the regular expression parser he had written for the UNIX ed utility.
199%In 1976, Aho improved upon Thompson's implementation that with a DFA-based implementation called egrep.
200%Egrep was faster then grep for simple patterns but for more complex searches it lagged behind because of the
201%time it took to build a complete finite automaton for the regular expression before it could even start searching.
202%Since grep used a nondeterministic finite automaton it took less time to build the state machine but more time
203%to evaluate strings with it. Aho later used a technique called cached lazy evaluation to improve the performance of egrep.
204%It took zero set-up time and just one additional test in the inner loop.
205
206%Source: Chapter 7 Flexible Pattern Matching \cite{navarro2000}. \cite{navarro2000}
207
208%Gnu grep
209%agrep
210%nr-grep
211%re2
212
213\section{Bit-parallel Data Streams}
214\label{Bit-parallel Data Streams}
215
216% Contrast 'bit-parallel data streams' with the bit-parallel simulation of automata.
217
218The bit-parallel data streams use the wide
219SIMD registers commonly found on commodity processors
220to process  byte positions at a time using
221bitwise logic, shifting and other operations.
222
223A signficant advantage of the bit-parallel
224data stream methods over other
225pattern matching methods that rely on
226bit-parallel automata simulation
227is the potential to skip register width
228characters. % reword
229
230Skip SIMD register width.
231
232\subsection{Match Star}
233
234%Source: http://en.wikipedia.org/wiki/Backtracking
235%Backtracking is a general algorithm for finding all solutions to some computational problem,
236%that incrementally builds candidates to the solutions.
237
238Match Star takes a marker bitstream and a character class bitstream as input.  It returns all positions that can be reached by advancing the marker bitstream zero or more times through the character class bitstream.
239
240Figure one illustrates the Match Star method.  The second and third rows are the input bitstreams: the initial marker position bitstream and the character class bitstream derived from the source data.
241
242In the first operation ($T_0$), marker positions that cannot be advanced are temporarily removed from consideration by masking off marker positions that aren't character class positions using bitwise logic.  Next, the temporary marker bitstream is added to the character class bitstream.  $T_1$ has 1s in three types of positions.  There will be a 1 immediately following a block of character class positions that spanned one or more marker positions, at any character class positions that weren't affected by the addition (and are not part of the desired output), and at any marker position that wasn't the first in its block of character class positions.  Any character class positions that have a 0 in $T_1$ were affected by the addition and are part of the desired output.  These positions are obtained and the undesired 1 bits are removed by XORing with the character class stream. $T_2$ is now only missing marker positions that were removed in the first step as well as marker positions that were 1s in $T_1$.  The
243output marker stream is obtained by ORing $T_2$ with the initial marker stream.
244
245\begin{figure}[tbh]
246\begin{center}
247\begin{tabular}{cr}\\
248source data & \verb--142578---125-231-----127--5394---94761205-\\
249$M_0$ & \verb.......1......1..1..1...1.............1..1..\\
250$D =$\verb:[0-9]: & \verb..111111...111.111.....111..1111...11111111.\\
251$T_0 = M_0 \wedge D$ & \verb.......1.........1......1.............1..1..\\
252$T_1 = T_0 + D$ & \verb.1.........1111.......1..1..1111..1...1...1.\\
253$T_2 = T_1 \oplus D$ & \verb.1111111......1111....111.........1111.111..\\
254$M_1 = T_2 \, | \, M_0$ & \verb.1111111......1111..1.111.........11111111..
255\end{tabular}
256
257
258\end{center}
259\caption{Match Star}
260\label{fig:scan1}
261\end{figure}
262
263\section{Compiler Technology}
264\label{Compiler Technology}
265%\input{compilertechnology.tex}
266
267\section{Methodology}
268\label{Methodology}
269%\input{methodology.tex}
270
271We compare the performance of our bit-parallel data stream techniques against
272several fast regular expression matching implemenations,
273Gnu grep, agrep \cite{Wu92agrep-}, nr-grep, and re2.
274
275\section{Experimental Results}
276\label{Experimental Results}
277%\input{results.tex}
278
279
280\input{GPUImpl.tex}
281
282\section{Conclusion}
283\label{Conclusion}
284%\input{conclusion.tex}
285{
286  \bibliographystyle{acm}
287  \bibliography{reference}
288}
289
290\end{document}
Note: See TracBrowser for help on using the repository browser.


text:
# 1029 Median （25 分）【边输入边输出】

1029 Median （25 分）

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

### Input Specification:

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×105) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

### Output Specification:

For each test case you should output the median of the two given sequences in a line.

### Sample Input:

4 11 12 13 14
5 9 10 15 16 17

### Sample Output:

13

#include<bits/stdc++.h>
using namespace std;
int v[200010];
int main(void)
{
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
v[n+1]=0x7fffffff;
scanf("%d",&m);//这句和下一句之前调换了位置就错了
int j=1,median=(n+m+1)/2,ans=0;
int temp;

for(int i=1;i<=m;i++)
{
scanf("%d",&temp);
while(v[j]<temp)
{
ans++;
if(ans==median) printf("%d",v[j]);
j++;
}
ans++;
if(ans==median) printf("%d",temp);
}
while(j<=n)
{
ans++;
if(ans==median) printf("%d",v[j]);
j++;
}
return 0;
}