Citation
Efficient algorithms for wildland fire simulation

Material Information

Title:
Efficient algorithms for wildland fire simulation
Creator:
Kondratenko, Volodymyr Y. ( author )
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
1 electronic file (96 pages). : ;

Subjects

Subjects / Keywords:
Flame spread -- Mathematical models ( lcsh )
Wildfires -- Mathematical models ( lcsh )
Algorithms ( lcsh )
Wildfire forecasting -- Mathematical models ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
In this dissertation, we develop the multiple-source shortest path algorithms and examine their application importance in real world problems, such as wildfire modeling. The theoretical basis and its implementation in the Weather Research Forecasting (WRF) model coupled with the fire spread code SFIRE (WRF-SFIRE model) are described. We present a data assimilation method that gives the fire spread model the ability to start the fire simulation from an observed forced perimeter instead of an ignition point. White the model is running, the fire state in the model changes in accordance with the new arriving data by data assimilation. As the fire state changes the atmospheric state (which is strongly effected by heat flux) does not stay consistent with the fire state. The main difficulty of this methodology occurs in coupled fire-atmosphere models, because once the fire state is modified to match a given staring perimeter, the atmospheric circulation is no longer in sync with it. One of the possible solutions to this problem is a formation of the artificial time of ignition history from an earlier fire state, which is later used to replay the fire progression to the new perimeter with the proper heat fluxes fed into the atmosphere, so that the fire induced circulation is established. In this work, we develop efficient algorithms that start from the fire arrival times given at the set of points (called a perimeter) and create the artificial fire time of ignition and fire spread rate history. Different algorithms were developed in order to suit possible demands of the user, such as implementation in parallel programming minimization of the required amount of iterations and memory use, and use of the rate of spread as a time dependent variable. For the algorithms that deal with the homogeneous rate of spread, it was proven that the values of fire arrival times they produce are optimal. It was also shown that starting from arbitrary initial state the algorithms have finite convergence and the amount of iterations was estimated. Application of the method on real tests, based on the data taken from the observed fires, has shown the high accuracy of the algorithm and its usefulness. Besides wildfire modeling, this technique has a high application value in different fields, such as epidemiology, demographics control, flood modeling, etc.
Thesis:
Thesis (Ph.D.)--University of Colorado Denver. Applied mathematics
Bibliography:
Includes bibliographic references.
System Details:
System requirements; Adobe Reader.
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Volodymyr Y. Kondratenko.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
911204660 ( OCLC )
ocn911204660

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

EFFICIENTALGORITHMSFORWILDLANDFIRESIMULATION by VOLODYMYRY.KONDRATENKO BachelorofScience,TarasShevchenkoKyivNationalUniversity,2008 MasterofScience,UniversityofColoradoDenver,2010 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoDenverinpartial fulllmentoftherequirementsforthedegreeof DoctorofPhilosophy AppliedMathematics 2015

PAGE 2

ThisthesisfortheDoctorofPhilosophydegreeby VolodymyrY.Kondratenko hasbeenapprovedforthe DepartmentofMathematicalandStatisticalSciences by JanMandel,Advisor JulienLangou,Chair LorenCobb AdamK.Kochanski WeldonLodwick April24,2015 ii

PAGE 3

Kondratenko,VolodymyrY.Ph.D.,AppliedMathematics EcientAlgorithmsforWildlandFireSimulation ThesisdirectedbyProfessorJanMandel ABSTRACT Inthisdissertation,wedevelopthemultiple-sourceshortestpathalgorithmsand examinetheirapplicationimportanceinrealworldproblems,suchaswildremodeling.ThetheoreticalbasisanditsimplementationintheWeatherResearchForecastingWRFmodelcoupledwiththerespreadcodeSFIREWRF-SFIREmodelare described. Wepresentadataassimilationmethodthatgivestherespreadmodeltheability tostarttheresimulationfromanobservedreperimeterinsteadofanignitionpoint. Whilethemodelisrunning,therestateinthemodelchangesinaccordancewith thenewarrivingdatabydataassimilation.Astherestatechanges,theatmospheric statewhichisstronglyeectedbyheatuxdoesnotstayconsistentwiththere state.Themaindicultyofthismethodologyoccursincoupledre-atmosphere models,becauseoncetherestateismodiedtomatchagivenstartingperimeter, theatmosphericcirculationisnolongerinsyncwithit.Oneofthepossiblesolutions tothisproblemisaformationofthearticialtimeofignitionhistoryfromanearlier restate,whichislaterusedtoreplaythereprogressiontothenewperimeterwith theproperheatuxesfedintotheatmosphere,sothatthereinducedcirculationis established. Inthiswork,wedevelopecientalgorithmsthatstartfromtherearrivaltimes givenatthesetofpointscalledaperimeterandcreatethearticialretimeof ignitionandrespreadratehistory.Dierentalgorithmsweredevelopedinorderto suitpossibledemandsoftheuser,suchasimplementationinparallelprogramming, iii

PAGE 4

minimizationoftherequiredamountofiterationsandmemoryuse,anduseofthe rateofspreadasatimedependentvariable.Forthealgorithmsthatdealwiththe homogeneousrateofspread,itwasproventhatthevaluesofrearrivaltimesthey produceareoptimal.Itwasalsoshownthatstartingfromarbitraryinitialstatethe algorithmshaveniteconvergenceandtheamountofiterationswasestimated. Applicationofthemethodonrealtests,basedonthedatatakenfromtheobservedres,hasshownthehighaccuracyofthealgorithmanditsusefulness.Besides wildremodeling,thistechniquehasahighapplicationvalueindierentelds,such asepidemiology,demographicscontrol,oodmodeling,etc. Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:JanMandel iv

PAGE 5

DEDICATION Dedicatedtomylovingparentsandsister. v

PAGE 6

ACKNOWLEDGMENT IwouldliketothankallthepeoplewhomIhavemetonmypathofgrowingasa mathematicianandascientist,andwithoutwhommythesiswouldneverhavebeen possible.Particularly,Iwishtothankmyteacher,Prof.ValentinLeifura,fromPetro MohylaMykolaivUniversity,whohelpedmeachievehighresultsintheUkrainian MathematicalOlympiadcompetitions,andmyundergraduateadvisor,Prof.Yuriy Krak,fromTarasShevchenkoKyivNationalUniversity.Iwouldliketothankmy graduateadviser,Prof.JanMandel,fromtheUniversityofColorado,forhiscontribution,encouragementandmentorshipthatgreatlyhelpedmetogrowasascientist andmadethecreationofthisthesispossible.Iwouldalsoliketothankmylovely parents,YuriyandGalyna,whoencouragedmetotaketherststepsinacademia, andmydearestsisterNinaforallhersupportandcompanionship.Finally,Ithank alltheprofessors,fellowstudentsandstaofthedepartmentofMathematicaland StatisticalSciencesfortheircompanyandcollaborationindiscussingvariousresearch ideasoverthepastseveralyears. vi

PAGE 7

TABLEOFCONTENTS Figures.......................................ix Chapter 1.Introduction...................................1 2.WildreModeling................................5 2.1CoupledModels.............................5 2.2PropagationMethods..........................7 2.3IgnitionProblemandAtmosphericBalance..............9 2.4WRF-SFIRESoftware..........................11 3.PropagationonaMesh.............................14 3.1ExistingMethods............................14 3.2DistanceBasedMethod.........................16 3.2.1ComputationalResults......................18 3.2.2Conclusion............................21 3.3ForwardMethod.............................22 3.3.1SimpleForwardPropagationAlgorithm............22 3.3.2FastForwardPropagationAlgorithm..............30 3.4BackwardMethod............................36 3.4.1SimpleBackwardPropagationAlgorithm...........36 3.4.2FastBackwardPropagationAlgorithm.............44 3.5TimeDependentMethod........................50 3.5.1BackwardPropagation......................50 3.5.2ForwardPropagation......................53 4.ApplicationtoFires:PerimeterIgnition...................56 4.1InitializationfromaFirePerimeter..................56 4.2CreatingArticialIgnitionTimeHistoryfromtheCurrentFire Perimeter.................................56 vii

PAGE 8

4.3EncodingandReplayingtheFireHistory...............57 4.4Results..................................58 4.4.1SantaAnaFires.........................58 4.4.2IdealCase.AlgorithmDrivenbyPureAtmosphericDatawith noFireInvolved.........................63 5.FastFourierTransformEnsembleKalmanFilterwithApplicationtoaCoupledAtmosphere-WildlandFireModel....................67 5.1DataAssimilation............................67 5.1.1FFTEnKFandCovarianceEstimationbyFFT........68 5.1.2MorphingEnKF.........................71 5.2ComputationalResults.........................72 5.3Conclusion................................72 6.ComputationoftheFuelFraction.......................76 6.1FuelFractionofthePartiallyBurningCell...............77 6.2Conclusion................................80 References ......................................81 viii

PAGE 9

FIGURES Figure 2.1One2 2tilewiththelowestlayeroftheatmosphericgridandthere meshonthesurfaceshown.Windvectorcomponents u v w arelocated atthemidpointsofthesidesoftheatmosphericgridcells.Reproduced from[24]....................................12 3.1Alevelsetfunctionlinearonthelinesegmentsconnectingthenodesof theremeshcannotbedenedatthenodes X and Y consistentlyasthe signeddistance.1fromtheinterface.Thedistanceofthepoint X from)-289(doesnotdependonthelocationofthepoint Z ,whilethedistance of Y does;yetthevaluesofthelevelsetfunctionat X and Y arelinear alongthesegment XY andsoxedbytheratiooftheirdistancesfrom W .Reproducedfrom[25]...........................15 3.2ConstructionofintersectionofthereperimeterandthehalflineoriginatingfromtheIgnitionpointandpassingthroughagivenmeshpoint. Reproducedfrom[20].............................18 3.3ThedierenceintheUandVwindcomponents,computedat6.1m,of thedirectsimulationminusthearticialpropagationat68minutes.Reproducedfrom[20]...............................19 3.4Therelativeerrorinthehorizontalwindspeedat6.1mabovetheground at68minutes.Reproducedfrom[20].....................20 3.5Thedirectresimulationat68minutes.Reproducedfrom[20]......20 3.6aThesituationwhenbothforwardandbackwardpropagationsgivethe sameresults.bSincetherearenooutgoingarrowsfromthepoint C thevalueoftherearrivaltimeatthispointwilldierforforwardand backwardpropagations............................40 ix

PAGE 10

3.7Firelineatstep t k ,wheretherecovereddistance d onthewayfrom point B topoint A d 0 = ROS t;C; ~ BA: ..................51 4.1 a Propagationofignitiontime t toanodefromneighboringnodesalreadyonre. b Backtrackingpropagationbackintimeofignition timetoanodefromneighboringnodeswheretherearrivedlater.Reproducedfrom[19]...............................59 4.2Perimeterofthe2007SantaAnaressimulationOctober22,2007 1PMPDT[19].Thereconsistedoftwores,WitchandGuejito,which startedonOctober21,200712:15PMPDTand22October20071:00 AMPDT,respectively,andsubsequentlymerged.Theasterisksandcirclesfromlefttorightindicatetherealandarticiallycalculatedignition pointsofGuejitoandWitchresrespectively.Reproducedfrom[19]...60 4.3Articialrearrivaltimefoundbyrepropagationbackintimefromthe reperimeterin4.2.Thetwopeaksonthebottom,markedbyarrows, arethetwoignitionlocationsandtimes,foundautomaticallyfromthe perimeter.Theverticalaxisandthefalsecolorarethetimefromthe beginningofthesimulation.Reproducedfrom[19].............61 4.4 a Horizontalwindat6.1minthe2007SantaAnaressimulationon October20071:00PMPDT. b Thesamewindasin a ,butwiththe articialignitiontimehistoryfromFig.4.3untilOctober20071:00PM PDT. c Thedierenceofaandb.TheRMSEis1.1 ms )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,whichis 8.8%ofthemaximalwindspeed12.53 ms )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Reproducedfrom[19]...62 x

PAGE 11

4.5 a Fireperimeterinthe2007SantaAnaressimulationon22October 22,20079PMPDT. b Thesameperimeterasin a ,butwiththearticialignitiontimehistoryfromsimulationdataFig.4.3onOctober22, 2007,1PMPDT.Thedierencesinthesimulation8hourslaterareonly minor,suchastheprotuberanceatthenortheastpartoftheperimeter. Reproducedfrom[19].............................63 4.6aTheignitionpointoftheredrivensimulation.bPerimeterofthe re,takenaftertheredrivensimulationwasrunningfor30minutes. Thefalsecolorrepresentstheamountoffuelburnt.Problemsetupand visualizationdonebyAdamKochanski...................65 4.7Articialrearrivaltimefoundbythebackwardrepropagationalgorithmwhichoriginatedfromthereperimeterin4.6bandwasusingno redrivenrateofspreadinaandredrivenrateofspreadinb.The verticalaxisandthefalsecolorarethetimefromthebeginningofthe simulation...................................65 4.8Firearrivaltimeoftheoriginalsimulation.bDierencebetweenre arrivaltimeoftheoriginalsimulation4.8aandonecomputedbythe backwardrepropagationalgorithmstartingfromtheperimeterandusing windsnotaectedbythereFigure4.7a................66 4.9Locationoftherealignitionpointredcircle,theonefoundwithperturbedwindsbluecircle,andtheignitionpointwithwindswithoutre blackcircleinrelationtothecontouroftheperimeter..........66 5.1ThemorphingKalmanFilterEnKFwith5ensemblemembers,applied tothegroundheatuxfromtheWRF-Firemodel.Theensemblesizeis notsucient,thecorrectanalysisisnotevenapproximatelyinthespan oftheforecast,andtheEnKFcannotreachit................74 xi

PAGE 12

5.2ThemorphingFFTEnKFwith5ensemblemembers,appliedtothe groundheatuxfromtheWRF-Firemodel.Theanalysisensemblemoved towardsthedata.Reproducedfrom[27]...................75 6.1Divisionofremeshcellsintosubcellsforfuelfractioncomputation. Thelevelsetfunction andtheignitiontime t i aregivenatthecenters a 1 ;:::; a 4 ofthecellsoftheregrid.Theintegral.5overthecell C withthecenter a 3 iscomputedasthesumofintegralsoverthesubcells C 1 ;:::;C 4 .Whilethevaluesof and t i areknownat a 3 = x 3 ,theyneed tobeinterpolatedtotheremainingcorners x 1 x 2 x 4 ofthesubcell C 1 fromtheirvaluesatthepoints a 1 ;:::; a 4 .Reproducedfrom[24]......79 xii

PAGE 13

1.Introduction Forestsplayaveryimportantroleinourplanet'secosystembymitigatingsuch ecologicalproblemsasairpollution,erosionandgroundwaterdeciency.However, wildresthatareapartofthenaturallifecycleofaforestcangetoutofcontroland causemajordamagetoforests,itsspeciesandendangerlivesandproperties. Wildlandreisacomplexmultiscaleprocess.Someaspectswildlandrebehavior canbecapturedbythecouplingofamesoscaleweathermodelwithasimple2Dre spreadmodel.Weatherhasamajorinuenceonthewildrebehavior.Inparticular, therespreaddependsonseveralfactors,suchaswind,atmospherichumidity,type offuel,topography,etc.Sections2.1and2.2provideanintroductiontodierent coupledatmosphere-remodelsandpropagationmethodsusedinwildremodeling. ThecoupledWRFandSFIREsoftware,describedinsection2.4,combinesthe WeatherResearch,ForecastingModelWRFandrespreadmodelSFIRE,is intendedtobefasterthanrealtimeinordertodeliveraforecast. TheoriginalignitionmechanismofWRF-FIREmodelallowsonlypointandline ignitions.However,usuallytheinitialinformationaboutthelocationofthere arriveswhentherehasalreadybeenburningforacertainperiodoftime.Inthat case,themodeleitherhastoguesstheignitionpoint,whichsignicantlydropsthe accuracyofthemodel,orhastosetthewholereperimeteronre,whichcausesthe inconsistencybetweentheatmosphericandrestates. Oneofthepossiblesolutionswouldbetogeneratethearticialrehistorybased onthegivenreperimeterandtime,thefuelmapandthestateoftheatmosphere inthetimeperiodbeforetheperimetertime.Usingoneoftherepropagation algorithmsdescribedinchapter3,thearticialtimeofignitionhistoryiscreatedand ishypothesizedtobeclosetotherealretimeofignition.Wethenusethearticial rearrivaltimeinsteadoftherespreadmodeltoburnthefuelandgeneratethe heatreleasetotheatmosphere.Replayingthearticialrehistoryenablesgradual 1

PAGE 14

fuelburn,insteadofignitingthewholeareainsidethereperimeteratonce.This processallowsthere-inducedatmosphericcirculationtodevelop.Attheperimeter time,thecompletecoupledatmosphere-remodeltakesover. Ourcurrentapproachconsistsofreversingthedirectionoftimeinarespread method,whichwillresultinshrinkingtheretooneormoreignitionpoints.` M thatdenesadirectedgraph G M ; E ,where E containstheedge AB if t AB < 1 HereAandBaretwoneighboringpoints, A;B 2M and E hasnoloopingedges t AA =0.Theshortestpathtothegivenpointistheminimaltraveltimealong theneighborsfromthecurrentreperimeter,suchthatthesumofweightsalong theedgesisminimized.Inchapter3wedevelopedthemultiple-sourceshortestpath algorithms,whicharesuitablefortimereversal.Themethodsdeterminetheignition timeatanodeastheearliesttimetherecangettothatnodefromthenodes thatarealreadyburning.Inparticular,inSection3.2,therearrivaltimesinsidea givenconvexorstar-shapedperimeterwereapproximatedbasedonthedistancefrom aknownignitionpointtotheperimeter,whileuseofthereinitializationequation wasproposedin[25].Intheidealcase,whereallthedataistakenfromthemodel simulationoutput,whichoriginatesfromapredenedignitionpointandwasusing thehomogeneousrateofspread,thesimulationresultsshowthattherecancontinue inanaturalwayfromadenedperimeter. Subsequently,theauthordevelopsmoreadvancedbackwardpropagationmethods usinghomogeneousinputdatainSection3.4,wheretwoalgorithmsweredeveloped toservedierentpurposes.Dataassimilationtechniques,whicharetheprocesses duringwhichnewdataisincorporatedintothemodel,requiretherealizationofthe forwardpropagationalgorithmsthataredescribedinSections3.3. Simpleforwardandbackwardpropagationalgorithmsdescribedin3.3.1and3.4.1 areconstructedinawaythatmakesthemsuitableforparallelcomputing,sincemost ofthecomputationscanbeperformedsimultaneously.Fastpropagationmethodsde2

PAGE 15

scribedinsections3.3.2and3.4.2aremoreecientintermsofspeed,memorysaving anddecreasingtheamountofiterations,howevertheconstructionofthealgorithms makesithardtoimplementthemforaparallelcomputing.Foralloftheabovealgorithmsitisshownthattheyconvergetoauniquexedpointinaniteamountof steps. Theadvantageofthemethodsdescribedinsection3.5isthattheylettherate oftherespreadtobeanonhomogeneoustimedependentvariable.Thismakes thesemethodsapplicableintherealworldproblems,wheresuchvariablesaswind andmoisturearechangingcontinuously. Simulationresultsintherealcasestudywereperformedwiththe2007SantaAna resseeSection4andtheerrorsinignitionpointlocationandignitiontimesmap betweenthesimulationresultsandobserveddatawerecomputed.Relativelysmall errorsdemonstratedthatthemodelthatusesthearticialrehistoryhasminor dierencesfromtheoriginalmodelthatstartsatthegivenignitionpoint. Insection4.4.2weproposethesimulationofanidealcasepresentinghowthe algorithmperformsincaseofabsenceofactualrepropagationsimulation.The resultsofusingthererateofspreaddata,notaectedbythere,inExtendedFast Backwardpropagationalgorithm,arenotasprecise,comparingtotheresultsbased ontheredrivendata.Thisshowsthattheimpactofthereeectonthewind playsanimportantroleforthebackwardrepropagationalgorithm. Chapters5and6talkaboutresearchprojectsecientfortheresimulation. Inparticular,inChapter5weproposeanewtypeoftheEnsembleKalmanFilter EnKF,whichusestheFastFourierTransformFFTforcovarianceestimation fromaverysmallensemblewithautomatictapering,avoidingtheneedtosolvea sparsesystemwithataperedmatrix.Chapter6describesthemethodoffuelfraction computation,whichisrealizedbyinterpolationofthetimeofignitionofthecell,for acasewhenthecellispartiallyburning. 3

PAGE 16

Partsofthisthesisarebasedonthefollowingpapers.Section2.1isbasedon papers[20]and[25].Section2.4andchapter6arebasedon[24].Section3.2isbased on[20].Sections3.3-3.5arenew.Chapter4isusingpartsof[19].Chapter5is basedon[26]. 4

PAGE 17

2.WildreModeling 2.1CoupledModels Wildlandreisacomplicatedmultiscaleprocess.Nowadays,awiderangeof wildlandrebehaviorpropertiescanbetrackedbycouplingofaweathermodelwith a2Drespreadmodel[6,8,7,9].Wildrebehaviorstronglydependsonweather conditions,inparticular,windandmoisturehaveahighimpactontherateofspread re.Ontheotherside,thereinuencestheweatherthroughtheheatandvapor uxescausedbyburninghydrocarbonsandevaporationofthefuelmoisture.The heatfromarecancausetornadicstrengthwinds,andthewindandthemoisture fromtherecanaecttheatmospherelayerslocatedawayfromthere. ThemodelconsideredherecouplestheatmosphericcodeWRF-ARW[37]with arespreadmoduleSFIRE.SFIREisbasedonmodiedRothermel'sformula[34], whichapproximatestherespreadrateinthenormaldirectiontotherelineasa functionoffuelproperties,thecomponentofthewindvectorinnormaldirectionclose totheground,andterrainslope: R =min f B 0 ;R 0 + W + S g ; where B 0 isthespreadrateagainstthewind, R 0 isthespreadrateintheabsence ofwind, W = a )778(! v )778(! n b isthewindcorrection,and S = d r z )778(! n istheterrain correction.Further, )778(! v isthewindvector, r z istheterraingradientvector,and )778(! n isthenormalvectortotherelinepointedawayfromtheburningarea. Reductionofthefuelmassduringburningisapproximatedasanexponential decayintime.Ateachtimestep,theremodelinputstheatmosphericwindsand outputsheatuxesintotheatmosphere.ThenestpossibledomaininWRFis coupledwiththeremodel.However,thereeectforinstancesmokeisalso visibleintheparentdomains. Foreachnodeoftheregridthestatevariablesoftheremodelarecalculated. Inparticular,levelsetfunction,timeofignition T i andremainingfuelfraction F are 5

PAGE 18

givenbytheirvaluesonthenodesoftheremodelmesh.Atagivensimulationtime t ,thereareaisrepresentedbythelevelsetfunctionasthesetofallpoints x;y where t;x;y 0.Theignitiontime T i = T i x;y hastosatisfytheconsistency conditions 8 > > < > > : T i x;y t; if x;y isburningattime t orhasburntalready T i x;y >t; if x;y wasnotsetonreyet ; .1 whichintermsofthelevelsetfunctioncanbedescribedas 8 > > < > > : t;x;y 0 ; if x;y wassetonrebeforetime t t;x;y 0if x;y wasnotignitedyet : .2 Eachtimestepofthesimulation,theadvanceofthelevelsetfunctioniscomputed byaRunge-Kuttaschemeforthelevelsetequation d dt = )]TJ/F19 11.9552 Tf 9.298 0 Td [(R jr j ; .3 where R = R t;x;y isthererateofspreadand jj istheEuclideannorm.From thelevel-setrepresentationoftherelineatthetime t ,as t;x;y =0,itfollows thatthenormaldirectionis r = jr j ,therefore R = R u r jr j ; .4 where u isthewindeld. Whilethefuelisburning,theremainingmassfraction F = F t;x;y isapproximatedbyexponentialdecay, F t;x;y = 8 > < > : F 0 x;y exp )]TJ/F20 7.9701 Tf 10.494 5.698 Td [(t )]TJ/F20 7.9701 Tf 6.587 0 Td [(T i x;y T f x;y ;t>T i x;y ; 1 ;t T i x;y ; .5 where T f isthefuelburntime,thatrepresentsthenumberofsecondsthattakesthe fueltoburndownto1 =e 0 : 3689ofthestartingfuelfraction F =1. 6

PAGE 19

Ateachtimestepoftheatmosphericmodelthewindsareinterpolatedfromthe atmosphericmodelgridtoanerremodelgrid.Anumericalschemeforthelevel setequation.3isthenadvancedtothenexttimestepvalue,andthefuel,burned duringthetimestep,iscomputedbytakinganintegralof.5ineachremodel cell.Theaverageoftheheatuxesiscalculatedovertherecellsthatmakeupone atmospheremodelcell. WRFcanberunwithseveralnestedreneddomains,whichcanrundierent physicalmodels.SFIREusestheWRFinfrastructureforparallelcomputingandfor datamanagement.Thecoupledcodeperformsfasterthanrealtimeandrequiresat leastseveralhundredcores,withtheremodelresolutionoffewmetersandhorizontalatmosphericresolutionontheorderof100m,foralargerealre[17].Another WRFfeatureistheabilitytoexportandimportstate,inordertoimplementdata assimilationinputofadditionaldatawhilethemodelisrunning,whichisessential forrebehaviorpredictionfromallthenewestavailabledata.FueldataandtopographycanbeobtainedfromgovernmentdatabasesintheUnitedStates,fromsatellite imagesandGISelsewhere[17],etc.ThemodelisavailablefromtheOpenWildland FireModelingenvironmentat openwfm.org ,alongwithutilitiesfordatapreparation, visualization,anddiagnostics. 2.2PropagationMethods Thematerialsinthissectionarepartiallyreproducedfrom[38]. Startinginthe1950s,considerableeortwasexpendedexploringtheeectsof themassbombingsthatoccurredduringWorldWarII,andthecollateralincendiary eectsofnuclearweapons.Thisresearcheortwascloselyrelatedtothatofforest resandhasresultedinaboominwildlandrebehaviorresearch. Modelingthebehaviorofwildreshasbecameaverypopulartopicoverthe pastfewdecadesduetoadvancesincomputationalpower.Dierentpropagation modelshavebeendevelopedandcanbedividedintothreemaincategories:Physical, 7

PAGE 20

EmpiricalandSimulationModels.Allofthemodelshaveamathematicalformand areinfactmathematicalmodels. Inthisthesis,wearemainlyfocusedonconstructingamathematicalmodelthat helpstoimprovethedataassimilationmethod.Dataassimilationneedstobeperformedwhenevernewdatacontaininganupdatedreperimeterarrivesandisbeing usedinacoupledre-atmospheremodel.Thesimulationmodelgenerallyimplements apre-existingrespreadmodelcanbephysicalorempiricalinsuchawayasto simulatethespreadofreacrossalandscape. Mathematicallyanalogousmodelsareusuallybasedonmathematicalconcepts thathavebeenappliedtowildlandrespread.However,becausethesemodelsare notdeliveredfromanyunderstandingofwildlandrebehaviorthatletsthismodels beappliedtootherelds,suchasepidemiology,oodstudies,etc. Ingeneral,therearetwoapproachesforthererepresentationthatareimplementedinsimulationmodels:rasterandvectorimplementation.Rasterimplementationdealswithareasagroupofindependentcellsthatgrowordecreaseinnumber astherepropagates.Vectorimplementationrepresentsreperimeterasasetof linkedpointsinashapeofaclosedcurve.Therearedierentpropagationmethods, whosepurposeistoimplementacertainextensionalgorithmtotheremodel,such asminimaltraveltime,levelsetmethod,methodoftracers,etc.Ingeneral,each propagationmethodislinkedwithaoneofthererepresentationmethods. Inrecentyears,ourteamwasusingarepropagationmethodbasedonthe levelsetfunction.Inthelevelsetfunctionstudiesimportantresultswereachieved byMallet[21]useshighorderENO-WENOmethod,Mandel[23]secondorder upwindingandRochoux[33]FluxlimiterandHamilton-Jacobiequation.Our methoddealswiththenon-homogeneousrateofspread,whichmakesitmorestable thanthelevelsetmethod. Inmymodel,Iamapplyingtheminimumtimetravelmethodtoarasterbased 8

PAGE 21

resimulationbasedontheRothermelspreadmodel.Asimilarapproachtoour methodhasJohnstonin[16].However,inourmethodwedonotapproximatethe rateofspread,assumingthatthereshapeisclosetoellipse,butcalculaterateof spreadbasedonRothermel'sformula.Unlike[16],whereallthepossiblestatesofthe cellandallpossibleresultingeventsarekeptinmemory,inourmethod,thestateof thecelliscontinuouslybeingupdatedtoitsoptimalvalue,whileallthenotsatisfying statesarebeinglteredoutintheearlierstage.Thismakesourmethodfasterand morememoryecient. OthermethodsthathaveasimilarideatoourmethodistheFastMarching MethodandthemethoddescribedbyFinneyin[14].However,thepartthatmakes ourmodeldierentisthatitcontinuouslyupdatesthetimeofignitionoftherearea usingallthevaryingvariables,suchaswind,moistureandslope. 2.3IgnitionProblemandAtmosphericBalance ThecurrentWRF-Firemodelstartstherefromagivenignitionpointatagiven time.However,usuallytherstdataarriveswhentherehasalreadybeenrunning forsometimeandthelocationoftheignitionpointinunknownandonlycurrent reperimeterisgiven.Ifthewholereareaissetonresimultaneously,thenthe atmospherestatewillbeincorrectandthecoupledatmosphere-remodelwillcrash. Thisproblemresultedinaneedfortheremodeltobeabletostarttherefrom agivenreperimeteratagiventimeinstead.Sincethefuelbalanceandthestate oftheatmospheredependonthehistoryofthere,thepurposeofthisworkisto createanapproximatearticialhistoryoftherebasedonthegivenreperimeter andtime,thefuelmap,andthestateoftheatmosphereduringtheperiodbeforethe perimetertime.Thehistoryisencodedastherearrivaltimeatthenodesofthe remodelmesh.Wethenusethearticialrearrivaltimeinsteadoftherespread modeltoburnthefuelandgeneratetheheatreleasetotheatmosphereupuntilthe rereachesgivenreperimeter.Replayingthearticialrehistoryenablesgradual 9

PAGE 22

fuelburn,insteadofignitingthewholeinsideofthereperimeteratonce,andthus allowsthere-inducedatmosphericcirculationtodevelop.Attheperimetertime, thecoupledatmosphere-remodeltakesover. In[20],therearrivaltimesinsideagivenperimeterwereapproximatedbased onthedistancefromaknownignitionpointtotheperimeter,whileuseofthereinitializationequationwasproposedin[25].Ourcurrentapproachconsistsofreversing thedirectionoftimeinarespreadmethodandshrinkingtheretooneormore ignitionpoints.Forthispurpose,wehavedevelopedanewrespreadmethod,which issuitablefortimereversal.Therepropagationmethods,developedinthisthesis, determinetheignitiontimeatanodeastheearliesttimetherecangettothat nodefromthenodesthatarealreadyburning.Suchmethodsareknownasminimal travelorminimalrearrivaltime[14].Dierentalgorithmsweredevelopedinorder tosuitpossibledemandsoftheuser,suchasimplementationinparallelprogramming, minimizationoftherequiredamountofiterationsandmemoryuse,anduseofthe rateofspreadasatimedependentvariable.Forthealgorithmsthatdealwiththe homogeneousrateofspread,itwasproventhatthevaluesofrearrivaltimesthey produceareoptimal.Itwasalsoshownthatstartingfromarbitraryinitialstatethe algorithmshaveniteconvergenceandtheamountofiterationswasestimated.Alist ofnodesontheboundaryofthealreadyburningregionismaintainedsimilarlyasin thefastmarchingmethod[35].However,thefastmarchingmethodcannotbeused, sinceitdependsonthecurrentwindspeeddrivingtherateofspreadinthesimulation,whileinremodelingtheretraveltimefromonenodetothenextchanges dynamically.Tobuildthearticialrehistory,wereversethedirectionofthetime andproceedfromtheperimetertotheinsideofthedomain. Replayingtherehistorythenestablishesareasonablefuelbalanceandoutputs heatuxesintotheatmosphericmodel,whichallowstheatmosphericcirculation todevelopproperly.Thenthecoupledatmosphere-remodelcontinuesfurtherre 10

PAGE 23

propagation. 2.4WRF-SFIRESoftware ThebackgroundinformationabouttheWRF-SFIREsoftware,describedinthis section,ismostlyreconstructedfrompapers[23]and[24]. ThecoupledWRFandSFIREcode[23]combinestheWeatherResearchand ForecastingModelWRFwithasemi-empiricalrespreadmodel.Itisintended tobefasterthanrealtimeinordertodeliveraforecast.Theoriginalsourceofthe codewastheNCAR'sCAWFEcode[8,6,7,9],whichconsistsoftheClark-Hall mesoscaleatmosphericmodel,coupledwithatracer-basedrespreadmodel.The mainadvantageoftheWRFmodelisthatitisparallelsupportedcommunitycode routinelyusedforrealruns[10],unliketheClark-Hall,whichisnotsupported,and isdiculttomodifyoruseforrealcasesrequiringrealmeteorologicaldata,topography,andfuelmaps.ThemodelwasstartedasWRF-Fireby[32],whoproposed acombinationofWRFwiththetracer-basedmodelfromCAWFE.Laterinstead ofusingtheexistingtracer-basedCAWFEcode,theremoduleSFIREwasdevelopedbasedonthelevelsetmethod[31].Amorecompletedescriptionisavailableat http://www.openwfm.org/wiki/OpenWFM_development_notes Therepresentationofthereregionbythelevelsetfunctionisconsideredtobe moreexiblethantherepresentationoftheburningregioninCAWFEbyfourtracers ineachcelloftheremesh,whichisoneofthereasonswhytherepropagation schemewasreplaced.Inparticular,thelevelsetfunctioncanbemaintainedmore easilythantracersforthepurposeofdataassimilation. SFIREisapublicdomainsoftwareanditisdistributedasWRF-FireintheWRF sourcecodeat http://wrf-model.org .Thereleasedversionisupdatedperiodically andsupportedbyNCAR.ThecurrentversionofSFIREisavailableandsupported at http://openwfm.org Theatmosphericmodeloperatesona3-DgridoftheEarthsurface,andusesa 11

PAGE 24

Figure2.1:One2 2tilewiththelowestlayeroftheatmosphericgridandthere meshonthesurfaceshown.Windvectorcomponents u v w arelocatedatthe midpointsofthesidesoftheatmosphericgridcells.Reproducedfrom[24]. sequenceofhorizontallynestedgrids,calleddomains.Onlytheinmostatmospheric domainiscoupledwiththeremodel.Scalarvariablesintheatmosphericmodel arelocatedatthecentersofthegridcells,whilethewindvectorcomponentsare givenatthemidpointsofthecellfaces.Thevariablesthattheremodeloperates onarerepresentedbytheirvaluesatthecentersofthecellsoftherenedremesh Fig.2.1. Tofuelspecicationsconsistof13categories[2],whicharepredenedvectorsof valuesofthefuelproperties.Theusercanmodifythesevaluesorspecifycompletely new,customfuelcategories.Therespreadmodeloperateswiththeaveragevalues offuelproperties. Parallelcomputing,whichisessentialforfastexecution,imposesasignicant impactonuserprogrammingtechnique.EssentiallyWRFparallelinfrastructure[30] dividesthedomainhorizontallyintorectangularregions,called tiles ,inawaythat dierenttilesareassignedtodierentprocessorcores,whichexecuteinparallel. WRFcoderunsonasingletile,usingvaluesfromstripsaroundthetileboundaryin neighboringtiles,ifnecessary.Adisadvantageoftheparallelcomputingstructureis 12

PAGE 25

thatitlimitstheclassofnumericalmethodsthatcanbeimplemented.Inparticular, high-ordermethods,whichneedtoupdatevaluesatanodeusingvaluesfromdistant nodesarenolongerverypractical,bothbecauseofthecomplexityofprogramming andbecauseofthesharplyincreasedcommunicationcost.Thisiswhynumerical methodsofthelowestpossibleorderareusuallymorepreferred. WRFmodelcanrunineither"ideal"or"real"mode.Theidealrunismostly usedfortestingpurposes.Particularlyitisusedtochecktheperformanceofthe modelwhendierentre-relatedcapabilitiesareadded.AWRFrealrunisusedfor forecastingandanalysisofnaturalevents. Amorecompletedescriptionisavailablein[24]. 13

PAGE 26

3.PropagationonaMesh 3.1ExistingMethods Onecommonlyusedlevelsetfunctionisthesigneddistancefromthegivenclosed curve, L x;y = dist x;y ; \051 ; .1 wherethesignistakentobenegativeinsidetheregionlimitedby)-415(andpositive outside[31],anddiststandsfortheEuclideandistance.Surprisingly,suchfunction cannotbedenedconsistentlyoncetheproblemisdiscretized.Consideralevelset function L thatisgivenbyitsvaluesonthecornersofgridcells,interpolatedlinearly alongthegridlines,and)-424(givenbyitsintersectionwiththegridlinesFig.3.1. Then,theratioofthevaluesof L attwoneighboringmeshcornersontheopposite sidesof)-410(isxedbytherequirementthat L islinearbetweenthetwocorners.In particular,itisnotpossibleingeneraltodene L asthesigneddistance.1.For example,inFig.3.1,theratio L X =L Y isxedand L X doesnotdependon Z ,while L Y does. Onepossibilityissimplydenethevaluesof L nextto)-318(bythesigneddistance, andforgetabouttheexactrepresentationof)-397(as L =0 : Instead,in[29],wehave proposedtondthevaluesof L nextto)-296(byleastsquares.Denotingby u thevector ofthevalues L nextto,itiseasytoseethat u satisesahomogeneoussystemof linearequationsoftheform Bu =0withatmosttwononzerosperrows,andeach rowcorrespondingtoanedgeonthemeshthatisintersectedby,astheedge XY Wecanthenndasuitable u minimizing k u )]TJ/F19 11.9552 Tf 11.955 0 Td [(d k 2 subjectto Bu =0,where d are thesigneddistances.1.Oncethevaluesof L near)-332(arefound,onecanextend L tothewholedomainasthedistancefunctionbytheFastMarchingMethodFMM [35],orbyasimplerandlessaccurateapproximatemethodsuggestedin[29]. Abettermethodcanbeobtainedbytakingthespreadrateintoaccount.The 14

PAGE 27

Figure3.1:Alevelsetfunctionlinearonthelinesegmentsconnectingthenodesof theremeshcannotbedenedatthenodes X and Y consistentlyasthesigned distance.1fromtheinterface.Thedistanceofthepoint X from)-410(doesnot dependonthelocationofthepoint Z ,whilethedistanceof Y does;yetthevaluesof thelevelsetfunctionat X and Y arelinearalongthesegment XY andsoxedby theratiooftheirdistancesfrom W .Reproducedfrom[25]. levelsetfunction L isasolutionoftheHamilton-Jacobiequation R j O L j =1 ;L =0on)]TJ/F19 11.9552 Tf 45.753 0 Td [(: whichcanbefoundbysolvingthereinitializationequation[31,Eq..4] @L @t = )]TJ/F19 11.9552 Tf 11.955 0 Td [(R j O L j .2 wherethesignistakenpositiveoutsideof)-373(andnegativeinside.Equation.2is solvedbyupwindingformulasmovingawayfrom)-381(andstartingfromthevaluesof L ontheothersideof.Alternatingthesolutionprocessbetweentheoutsideand theinsideof,thevaluesof L onthetwosidesof)-310(balanceoutandasteady-state signeddistancefunctionisobtained"[31,p.66]. Thesituationhereismorecomplicated,becausethespreadrate R dependson 15

PAGE 28

thelevelsetfunction L following.4.Hence,wefreeze L inside R andusesuccessive approximationsoftheform @L k +1 @t = 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(R u O L k j O L k j j O L k +1 j : L> 0outsideof P ;L< 0insideof P ;L =0on P : .3 Amongtheothermethodsthatwereintroducedinthepastfewdecadeweshould noteRehmat[33],wherethesecondorderedmethodanduxlimitingschemesare beingused.Abigvarietyofthelevelsetmethodsandfastmarchingmethodsused fortheinterfaceadvancementaredescribedbySethian[36]. 3.2DistanceBasedMethod Thissectionisbasedon[20].Thepurposeofthedistancebasedalgorithm, describedlaterinthissection,istocreatearticialvaluesofthethetimeofignitionon theremodelmesh,givenignitionpoint x ign y ign ,ignitiontime T ign ,reperimeter ,andthetimewhentherereachedtheperimeter T per ,assumingthatthere perimeterisconvex,oratleaststar-shapedwithrespecttotheignitionpoint.The reperimeterisgivenasasetofpoints x k ;y k intheremodeldomain, k =1 ;:::;n whichformaclosedcurveconsistingoflinesegments[ x k ;y k ; x k +1 ;y k +1 ]between eachtwosuccessivepoints.Wetake x 1 ;y 1 = x n +1 ;y n +1 sothatthestartingand theendingpointareidentical.Thecoordinatesofthepointofignitionandofthe pointsdeningofthereperimeterdonotneedtocoincidewithmeshpointsofthe grid. Themethodconsistsoflinearinterpolationoftheignitiontimebetween T ign attheignitionpointand T per ontheperimeter,alongstraightlinesconnectingthe ignitionpointwithpointsontheperimeter.Theignitiontimeisalsoextrapolated beyondtheperimeterinthesamemannertoprovideasuitablelevelsetfunction,as discussedintheprevioussection.Givenameshpointwithcoordinates x;y ,the algorithmtodeterminetheignitiontime T i x;y consistsofthefollowingsteps. 16

PAGE 29

1.Findtheintersection x b ;y b ofthereperimeterandthehalf-linestarting attheignitionpointandpassingthroughthepoint x;y Fig.3.2.Forthis purpose,weusethefunction F x;y;x b ;y b = y b )]TJ/F19 11.9552 Tf 11.955 0 Td [(y ign x )]TJ/F19 11.9552 Tf 11.955 0 Td [(x ign )]TJ/F15 11.9552 Tf 11.955 0 Td [( x b )]TJ/F19 11.9552 Tf 11.955 0 Td [(x ign y )]TJ/F19 11.9552 Tf 11.955 0 Td [(y ign ; whichiszeroifpoint x b ;y b liesonthelinedenedby x;y and x ign ;y ign ,and itispositiveinonehalf-planeandnegativeintheother.Wethenndsegment [ x k ;y k ; x k +1 ;y k +1 ]suchthat F x;y;x k ;y k F x;y;x k +1 ;y k +1 < 0thatis,the points x k ;y k and x k +1 ;y k +1 lieonoppositesidesofthelinepassingthrough x;y and x ign ;y ign .Sincethelineintersectsthereperimeterattwopoints, oneoneachsideoftheignitionpoint,wechoosecorrectsegmentasfollows: If x;y isinside)-284(thatis,closertotheignitionpointthantotheintersection,thenthedesiredsegmentistheonethatliesonthesamesidefrom theignitionpointasthepoint x;y ; If x;y isoutsideof,thentheneededsegmentliesonthesamesidefrom theignitionpointas x;y 2.Calculatethetimeofignitionofthemeshpoint,basedontheratioofthe distancesofthemeshpointandtheperimeterpointtotheignitionpoint, T i x;y = T ign + k x;y )]TJ/F15 11.9552 Tf 11.955 0 Td [( x ign ;y ign k k x b ;y b )]TJ/F15 11.9552 Tf 11.956 0 Td [( x ign ;y ign k T per )]TJ/F19 11.9552 Tf 11.955 0 Td [(T ign : 17

PAGE 30

Figure3.2:ConstructionofintersectionofthereperimeterandthehalflineoriginatingfromtheIgnitionpointandpassingthroughagivenmeshpoint.Reproduced from[20]. 3.2.1ComputationalResults Wehavetestedthisalgorithmonanidealexampletomeasurethedierencein theatmosphericwindsbetweenasimulationpropagatednaturallyfromapointand anotheroneadvancedarticially.Inthisexample,thetopographywasatexceptfor asmallhillroughly500mindiameterand100mhighinthecenterofadomainof size2 : 4km 2 : 4km.Theatmosphericandregridresolutionsusedwere60mand 6mrespectively,witha0 : 25stimestep.Thebackgroundwindswereapproximately 9 : 5m/sblowingtowardssouthwestattheatmosphericlayer6 : 1 m mabovethesurface. Therstsimulationwasignitedfromapointinthenortheastcornerofthedomain 2secondsfromthestart,andthereperimeterwasrecordedafter40minutes.This perimeterandignitionlocationwereusedtogenerateanarticialhistoryforthe rst40minutes,whichwasreplayedinthesecondsimulation.Therefore,there perimetersinbothsimulationsareidenticalat40minutes.Bothsimulationswere thenallowedtoadvanceanother28minutes,usingthestandardcoupledmodel.The 18

PAGE 31

outputswerethencollectedforanalysis. InFig3.5,weshow3Drenderingsofthesimulation.Thestreamlines,thatindicatethewinddirectionnearthesurface,showtheupdraftcreatedasaresultofthe heatoutputduetotheimpactofthehillandofthere.Thereisaectingtheatmospheredespitebeingpropagatedarticially.Asemi-transparentvolumerendering ofVAPORVisualizationandAnalysisPlatformforOcean,Atmosphere,andSolar Researcherswasaddedtosimulatethesmokerelease.InFig.3.3,thedierences inthewindbetweenthetwosimulationsat68minutesandthereperimeterare shown.Fig.3.4showstherelativeerrorinthewindspeeddenedasthenormofthe dierencefromFig.3.3,dividedbythewindspeedfromthedirectsimulation.This showsthatthemaximumerrorattheendofthis68minutesimulationislessthan 2 : 5%.Onthegurebelowredandgreencontoursrepresenttheburningareaandthe areathatwasnotsetonreyetrespectively. Figure3.3:ThedierenceintheUandVwindcomponents,computedat6.1m,ofthe directsimulationminusthearticialpropagationat68minutes.Reproducedfrom [20]. 19

PAGE 32

Figure3.4:Therelativeerrorinthehorizontalwindspeedat6.1mabovetheground at68minutes.Reproducedfrom[20]. Figure3.5:Thedirectresimulationat68minutes.Reproducedfrom[20]. 20

PAGE 33

3.2.2Conclusion Inthispreliminaryinvestigation,theignitiontimesinthereareaarecalculated basedonthedistancefromtheignitionpointtotheperimeter,assumingthatthe perimeterisconvexorstar-shaped.Simulationresultsforanidealexampleshowthat therecancontinueinanaturalwayfromtheperimeter.Possibleextensionsinclude algorithmsformoregeneralperimetersandrunningtheremodelbackwardsintime fromtheperimetertocreateamorerealistichistory. 21

PAGE 34

3.3ForwardMethod 3.3.1SimpleForwardPropagationAlgorithm Forthepropagationmethods,describedinthefollowingchapters,thedatais takenoutof wrfout les,however,dierentsourcescanbeusedasaninputdata. Theretraveltimes t AB arecomputedfromtheratesofspreadinthe8directionsto neighbors,storedinarrays F ROS11 ,..., F ROS33 .Anextensionofthealgorithm,tobe describedlater,willtakeintoaccountthattheratesofspreadchangewithtime,and sotheretraveltimesareactuallyfunctionsoftime.Thestructureofthealgorithms allowsapointofthemeshtohaveanarbitraryamountofneighbors,whichmakes themapplicablefordierentmeshesandconnectivity.Wewanttondthetimeof ignitionastheminimaltraveltimealongtheneighborsfromthegivenreperimeter. Thegoalofthealgorithmistocreateanarray t oftherearrivaltimesatthepoints inthemesh M ,fromthegivenreperimeterandrateofspread.Therateofspread givesthetraveltime t AB > 0betweentheneighborsAandB.Ateachpoint B of themesh, t B istheminimalretraveldistancefromtheneighbors.Thearrayof theminimaltraveltimeateverynodesatises: t B =min 8 A 2O B t A + t AB ; .4 where O B isasetofallneighborsofthepoint B Theareaofthere F isgiven.Theboundaryof F ,calledaperimeterofthere P ,consistsofallthepointsin F ,whichhaveatleastoneneighborin MnF .The valuesoftimeofignition t aregivenon P Putting 8 A= 2O B ; t AB = 1 ; wecanreplace.4with t B =min A t A + t AB : .5 22

PAGE 35

Denition3.3.1 Themeshoutsideofthereperimeterdenesadirectedgraph G N ; E ,where N = MnF [P ,and E containstheedge AB if t AB < 1 whereAandBaretwoneighboringpoints, A;B 2N and E hasnoloopingedges t AA =0 Therefore,wearelookingfortheminimalarrivaltimeinthesenseofthefollowing denition. Denition3.3.2 Foranypoint A ,theminimalarrivaltime A isdenedby A =min f t 0 A 0 + n X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i j A 0 2P ; A 1 ;:::;A n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 2NnP ;A n = A; 0 n m g where m isthenumberofpointscontainedintheset MnF Denition3.3.3 Wecallpoint A 2N reachablefrom P ifthereexistsapath alongtheedgesofthegraph G fromoneoftheverticesin P tothepoint A ,andcall it notreachablefrom P otherwise. Remark3.3.4 Ifpoint A is reachablefromthe P ,thenthereexistsatleastone neighbor B of A ,suchthat t BA < 1 .Ifpoint A is notreachablefromthe P thenoneoftwocasesispossible 1. 8 B 2O A : t BA = 1 2. A 2C ,where C2F isaclosedcurve,suchthat 8 C 2C and 8 B 2FnC : t BC = 1 : Denition3.3.5 Let V denoteasetofallvectorsin R m [f1g ,where m isthe numberofpointscontainedintheset N .Letusdenoteby t k B theentryofthe state t k thatcorrespondstothepointB,where t k 2 V isthestateofthealgorithm thatwascomputedduringthe k -thiteration. 23

PAGE 36

Denition3.3.6 Wewilldenoteby W 2 V asetofvectors,s.t.forany u 2 W u B = 1 foranypointBthatisnotreachablefrom P Inthefollowingalgorithm,duringeachiteration,thetimeofignitionofallthe pointsonthemeshisbeingupdatedfromitsneighborsusingformula.5.Such constructionofthealgorithmisveryconvenientforparallelcomputing,sincemostof thecomputationscanbeperformedsimultaneously. Algorithm3.3.7ForwardPropagationoftheFire Givenaretheperimeter oftherearea P ,theareaoutsideofthereregion N ,spreadrate t AB forall AB 2E ,and t 0 B 2 R forall B 2P .Initially t 0 B 2 ; + 1 ] forall B 2 NnP Fork=1,2,... Forallpoints B 2NnP t k B =min A 2O B f t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 A + t AB g .6 end end Lemma3.3.8 Algorithm.3.7denesamapping : W W by t k = t k +1 Proof: Weneedtoshowthatfor t k 2 W ;t k +1 = t k 2 W .Usingthedenitionof W .3.6,itfollowsfromremark3.3.4and.6that t k +1 2 W Wewillshowthatthemappingismonotonousinthepartialorderingon W u v 8 B 2N : u B v B .7 forany u;v 2 W Lemma3.3.9 Forany u;v 2 W :if u v ,then u v : 24

PAGE 37

Proof: Let u = u k v k = v ,thenbydenitionforall A 2N u k A v k A Since u k = u k +1 and v k = v k +1 ,thenfrom.6,forall B 2NnP u k +1 B v k +1 B .Inaddition,forall B 2P u k +1 B = v k +1 B andthus u v : Lemma3.3.10 Themapping issequentiallycontinuouson W Proof: Supposethatforany A 2N t k 2 W lim k !1 t k A = t A ; where t A 2 ; + 1 ] : Letusdenote t k = u k ,thenitfollowsfrom.3.8that forany B 2NnP u k B =min A 2O B f t k A + t AB g ; where O B isaniteset.Then lim k !1 t k A = t A = lim k !1 t k A + t AB = t A + t AB : Sincetheminimumistakenovertheniteset,then lim k !1 min A 2O B f t k A + t AB g =min A 2O B f t A + t AB g = = lim k !1 u k B = u B Thenextlemmashows,inparticularthatthexedpointofthemapping on W ifitexistsisunique. Lemma3.3.11 If t = t t 2 W ,thenforany A from N t A istheminimal arrivaltimeatthepoint A Proof: Foreverypoint A 2N ,denote L A thesmallestlength n ofthepath forwhichtheminimumisachievedinthedenition3.3.2ofthearrivaltimeofA. Theproofwillproceedbyinductionon n .Let n =0,thenallthepoints A forwhich 25

PAGE 38

L A =0arelocatedin P andsoitfollowsfromdef.3.3.2that A = t 0 A : For thecasewhen n =1,let A 2N ,s.t. L A =1,then A =min A 0 t A 0 + 1 X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A 1 = A = =min A 0 f t A 0 + t A 0 A 1 ;A 0 2P ;A 1 = A g = t A : Supposethatthestatementholdsforallpoints A ,suchthat L A = k thatis, t A = A =min A 0 ;:::;A k )]TJ/F18 5.9776 Tf 5.757 0 Td [(1 t A 0 + k X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A k = A For n = k +1let A 2N ,suchthat L A = k +1, A =min A 0 ;:::;A k t A 0 + k +1 X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A k +1 = A ; where A k canbeonlytakenfromthesetofneighborsof A ,suchthat L A k = k hence A =min A 0 ;:::;A k t A 0 + k X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i + t A k A k +1 ;A 0 2P ;A k +1 = A;L A k = k = =min A k A 2E f A k + t A k A g =min A k A 2E f t A k + t A k A g = t A : Inthetheorembelowwewanttoprovethatmapping hasauniquexedpoint. Inordertodothat,letusrstdenethesequences u k and w k anddescribetheir properties. Denition3.3.12 Denethesequence w k by w 0 B = 8 > > > > > > < > > > > > > : t 0 B ; 8 B 2P min f t 0 A j A 2NnPg ; 8 B 2NnP reachablefrom P 1 ; 8 B 2NnP notreachablefrom P .8 and w i = w i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 26

PAGE 39

Denition3.3.13 Denethesequence u k as u 0 B = 8 > > < > > : t 0 B ; 8 B 2P 1 ; 8 B 2NnP .9 and u i = u i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Lemma3.3.14 Thesequence w k ismonotonicallyincreasing. Proof: From.6,forany B 2NnP w 1 B w 0 B =min f t 0 A j A 2NnPg andthus w 1 w 0 .Fromthemonotonicityof Lemma3.3.9wegetbyinduction thatforany k w k w k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 andthereforesequence w k ismonotonicallyincreasing. Lemma3.3.15 Thesequence u k ismonotonicallydecreasing. Proof: From.6,forany B 2NnP u 1 B u 0 B = 1 andtherefore u 1 u 0 .Byinduction,Itfollowsfromthemonotonicityof Lemma 3.3.9thatforany k u k u k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,andthussequence u k ismonotonicallydecreasing. Theorem3.3.16 Forany t 0 2 W ,thesequence f t k g ,denedby t k = t k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,convergestotheuniquexedpointofthemapping on W Proof: Firstweshowthatthesequence t k convergestoaxedpointof on W byboundingtheiterations t i bylowerandupperstates w i and u i ,denedby.3.12 and.3.13,respectively,andwhichwillconvergemonotonouslytoxedpoints w and u as i !1 .Theuniquenessofthexedpointwillconcludetheproof. Sequences w 0 and u 0 bound t 0 frombelowandabove w 0 t 0 u 0 : 27

PAGE 40

ByinductionandfromtheLemmas3.3.14and3.3.15,wegetthat w i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 w i t i u i u i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ; .10 forall i =1 ; 2 ;::: Ifthepoint B 2NnP isnotreachablefrom P thenforall i w i B = t i B = u i B = 1 : Inthecasewhenthepoint B isreachablefrom P ,then,sincethesequence f u i B g ismonotonicallydecreasingandboundedbelowby w 0 B ,ithasalimit u B .Consequently, lim i !1 u i = u;u 2 W .11 and,since u i +1 = u i andthemapping issequentiallycontinuousLemma3.3.10, itfollowsthat u = u Since w i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 w i forall i 1by3.3.14,forany B 2NnP ,thesequence f w i B g isnondecreasingandisboundedaboveby u by.10and3.11,therefore lim i !1 w i B exists.Dening w bythislimit,wehave lim i !1 w i = w;w 2 W : Again,from w i +1 = w i andthesequentialcontinuityofthemapping on W ,we have w = w ItfollowsfromLemma3.3.11thatthexedpointof isunique,andthus u = w Therefore,bythesqueezetheorem,lim i !1 t i = u Theorem3.3.17 Forany t 0 2 W thesequence f t k g ,denedby t k = t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,convergesinanitenumberofsteps. Proof: Forany A 2N andforany i t i A min f t 0 B j B 2Ng .By denitionof W ,anystate t 0 u 0 ,where u 0 isdenedin.9.Fromlemma3.3.18 28

PAGE 41

itfollowsthatthereexists n m ,suchthat u n A < 1 forallAthatarereachable from P .Itfollowsfrom.10that t i u n ; 8 i n .Thereforeforany A 2N andfor all i n u n A t i A min f t 0 B j B 2Ng ; .12 where n m .Itfollowsthatforanypoint A reachablefrom P ,thevalue t k A is boundedbelowandabovebyconstantsandcanonlytakeanitenumberofvalues. ThereforeforeverypointA,reachablefrom P ,thevalue t i A reachesitsminimal arrivaltime A inthenitenumberofsteps i .Sinceforallthepointsthatare unreachablefrom P ,theirtimeofignitionstaysequalto 1 thatcompletestheproof. Inthecasewhenthestate t 0 isinitializedsothat t k ismonotonicallydecreasing with k ,thenumberofstepsofAlgorithm3.3.7isboundedbythenumberofnodes. Thiswillbethecase,inparticular,if t 0 A = 1 forall A 2NnP Lemma3.3.18 Supposethat t 0 2 W t k = t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 forall k 1 ,and t 0 t 1 .Then, foranypoint A 2N ,whichcanbereachedfrom P byapathwith k edges, t k A =min A 0 ;:::;A n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 t 0 A 0 + n X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A n = A;n k .13 Inparticular, t k equalstotheuniquexedpointof on W forsome k m Proof: Inordertoprovethetheorem t k needstobemonotonicallydecreasing with k ,whichissatisedsince t 0 t 1 .Wewillshow.13byinduction.First,for k =1. Forany A 2N ,whichhasaneighborfrom P : t 1 A =min A 0 2O A f t 0 A 0 + t A 0 A g t 0 t 1 =min A 0 2P f t 0 A 0 + t A 0 A g : Supposethatthestatementholdsfor k andnowweneedtoproveitfor k +1.By thedenitionofthemapping .3.8: t k +1 A =min B 2O A f t k B + t BA g : 29

PAGE 42

Substituting.13for t k B weget t k +1 A =min B 2NnP 8 > > < > > : min 8 > > < > > : t 0 A 0 + n X i =1 t A i )]TJ/F18 5.9776 Tf 5.757 0 Td [(1 A i ;A n = B; A 0 2P ;A 1 :::;A n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 2NnP ;n k 9 > > = > > ; + t BA 9 > > = > > ; t 0 t 1 =min 8 > > < > > : t 0 A 0 + n +1 X i =1 t A i )]TJ/F18 5.9776 Tf 5.757 0 Td [(1 A i ; A 0 2P ;A 1 :::;A n 2NnP ;A n +1 = A;n +1 k +1 9 > > = > > ; : 3.3.2FastForwardPropagationAlgorithm ThemainfeatureoftheFastForwardPropagationAlgorithmisthatitonlyuses thepoints,whichtimeofignitionwaschangedrecentlytoupdatethevaluesoftimeof ignitionoftheirneighbors.Thismethodisecientintermsofspeed,savingmemory anddecreasingtheamountofiterations,howevertheconstructionofthealgorithm makesithardtoimplementforaparallelcomputing. Algorithm3.3.19FastForwardPropagationoftheFire Givenarerearea FM ,itsperimeter PF ,andtheignitiontimes t 0 B = T forall B 2P 1.Initializetheauxiliaryset D 0 = P .Forallpoints A= 2P ,set t 0 A = 1 2.For k =1 ; 2 ;::: 3.Initializethesetofpointsthatwereupdatedinthiscycle, D k = ; 4.Forall B f B := t k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 B : 5.Forall A 2D k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 forallneighbors B of A if t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 A + t AB
PAGE 43

6.Forall B t k B = f B : 7.If D k 6 = ; Repeatfromstep2. else D k = ; thatis, t hasnotchangedinstep5, EXIT Lemma3.3.20 Thealgorithmdenesamapping on W ,by t k = t k +1 ismonotonicallydecreasinganditsrangeisin W Proof: Asitfollowsfromtheequations.14and3.15,foreachentry B ofthe state t k ,thevalueof t k +1 B canonlydecreaseorstayunchanged,whichproofsthe monotonicdecreaseof Inordertoshowthattherangeof isin W ,weneedtoprovethatforall B not reachablefrom P t k B = t k +1 B = 1 ,whichfollowsfromtheremark3.3.4and .14,3.15. Theorem3.3.21 Thesequence t k denedbyAlgorithm3.3.19converges. Proof: Since isamonotonicallydecreasingmapping,itfollowsthatforany A 2N t k A ismonotonicallydecreasingwith k .Since t k A isalsoboundedbelow by0,thesequenceconverges. Denition3.3.22 Foreveryiteration k oftheAlgorithm3.3.19theset U k isdened insuchway: 1. U 0 = P ; 2.If D k 6 = ; :Finda B k ,s.t. t k B k =min f t B j B 2NnU k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 g .17 U k = U k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 [f B k g ; 31

PAGE 44

3.If D k = ; : U k = N : Denition3.3.23 Point A iscalled permanentatstep l ifforany i>l : t l A = t i A : Theorem3.3.24 Algorithm3.3.19isnite. Proof: InthefollowingLemma.3.25wewillshowthat U l isasetthatonly consistsofpermanentpointsatthestep l .Accordingtothestep3ofthedenition 3.3.22,thesetofpermanentpointsincreasesatleastbyonepointateachstep.As such,thealgorithmwillbenitesincethesizeofthemeshisnite. Lemma3.3.25 8 n 8 k>n forany B 2U n : B= 2D k Proof: Theproofisbyinductionon n : 1.For n =0,initially U 0 = P .Sincethetimeofignitionofthepointsonthe perimeterissetandcannotbeupdatedduringthealgorithm,thusnopoint from P canbein D k forany k> 0. 2.Supposethatthestatementholdsforallthecyclesupto n )]TJ/F15 11.9552 Tf 12.772 0 Td [(1.FromDef. 3.3.22,aftertheendofthecycle n B n 2 argmin f t n A j A 2NnU n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 g ; .18 and U n = U n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 [f B n g Bytheinductionassumption, P ;B 1 ;:::;B n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = 2D k forall k>n )]TJ/F15 11.9552 Tf 12.223 0 Td [(1,andso, theycannotbeusedtoupdatethevalue t atthepoint B n atanycycle k>n Let A 2NnU n = NnfP ;B 1 ;:::;B n g .Wewanttoshowthat t i A t n B n forall i>n ,and,thus, A cannotbeusedtoupdatepoint B n inanycycle i>n either,sinceitwillnotsatisfytheinequality.14. aIf A= 2D i forall i>n ,then t i A = t n A t n B n by.18. 32

PAGE 45

bAssumethat A 2 D i forsome i>n ,andsousingformula.15, A here A = A i wasupdatedfromsomepoint A i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 2D i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,whichwas previouslyupdatedfromsome A i )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 2 D i )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 ; e.t.c.,untilsome A n +1 2 D n +1 wasupdatedfromsome A n 2 D n .Then, t i A i t i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 A i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 t n A n t n B n ; because t n B n wastheminimalfrom.18. Hence, t i A couldnotbeusedtoupdate t at B n .Since A wasarbitrarychosen from NnU n ,therefore, B n wasneverupdatedinacycle k>n ,thatis, B n = 2D k forall k>n Theorem3.3.26 Algorithm3.3.19generatesvaluesof t whichsatisfy.5forall pointsin N Proof: LetsassumethatAlgorithm3.3.19isnishedatstep i ,butthereisa point B and A 2O B ,suchthat t i A + t AB
PAGE 46

Theorem3.3.27 Supposethat t 0 on P and t 0 A = 1 forallthepoints A 2NnP ThenAlgorithm3.3.7andAlgorithm3.3.19producethesamesequenceofstates. Proof: Denesequence v k byAlgorithm3.3.7, v k = v k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 andsequence u k by Algorithm3.3.19, u k = u k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,sothat u 0 = v 0 = t 0 .Inordertoprovethetheorem, weneedtoshowthat v k = u k forany k .Theproofwillproceedbyinductionon k 1.For k =0theprooffollowsfromthedenition: u 0 = v 0 2.Supposethat v k = u k ,thatis, 8 B 2N : v k B = u k B 3.Tonishtheproofweneedtoshowthat v k +1 = u k +1 Assumethatthereexistsapoint B ,suchthat v k +1 B 6 = u k +1 B .Accordingto.6 inAlgorithm3.3.7, v k +1 B =min A 2O B f v k A + t AB g = v k A 0 + t A 0 B ; .21 forsome A 0 2O .InAlgorithm3.3.19,thevalueof u k +1 B canonlybeupdatedto itsnalvaluein.15fromoneoftheneighbors A 00 ofthepoint B ,andso u k +1 B = u k A 00 + t A 00 B = v k A 00 + t A 00 B min A 2O B f v k A + t AB g = = v k A 0 + t A 0 B = v k +1 B Sincebyassumption v k +1 B 6 = u k +1 B ,then u k +1 B >v k +1 B : .22 1.Assumethereexistsanindex i k ,suchthat A 0 2D i .Let j bethelargest suchindex.Thatis, A 0 2D j ,where j k ,and A 0 = 2D i forany i j
PAGE 47

Butthen,since A 0 2O B and j k u k +1 B : 3 : 20 u j +1 B : 14 ; 3 : 15 u j A 0 + t A 0 B : 23 = : 23 = u k A 0 + t A 0 B = v k A 0 + t A 0 B : 21 = v k +1 B ; whichcontradicts.22 2.Otherwise,assumethat A 0 = 2D i forall iv k +1 B : 21 = v k A 0 + t A 0 B =.27 = u k A 0 + t A 0 B : 26 = u 0 A 0 + t A 0 B = 1 ; .28 whichisacontradiction. Therefore,forany A in NnP itfollowsthat v k +1 A = u k +1 A andthatcompletes theproof. 35

PAGE 48

3.4BackwardMethod 3.4.1SimpleBackwardPropagationAlgorithm Thegoalofthebackwardpropagationalgorithmistoreconstructanarray t of therearrivaltimesfromitsvaluesontheperimeter P oftherearea F ,given therateofspreadofthereateachpointof F .Forthispurposeassumethat t is obtainedfromforwardpropagation,startingfromtheignitionpointthathasreached itsxedpoint, t = t Recallequation.5 t B =min A t A + t AB : Thatis,therespreadsfrompoint A topoint B duringtheforwardpropagation.It followsthat 8 C : t B t C + t CB .29 whichmeansthattherewouldarriveatthesametimeorlaterifitpropagatedfrom anyotherpoint,besides A .From.29weget 8 C : t B )]TJ/F15 11.9552 Tf 11.955 0 Td [( t CB t C : .30 Since 8 A= 2O B t AB = 1 weget t A max B 2F t B )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB =max B 2O A t B )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB ; .31 Remark3.4.1 If t A < max B 2F t A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB ,thentherewouldgettooneofthe neighborsofthepoint B tooearly,whichwouldleadtotheincorrectapproximation oftherearrivaltimes. 36

PAGE 49

Motivatedby.31wedene t b B astheminimumtimeatwhichtherecan arrivetothepoint B ,sothatitstillgetstoitsneighborsintime. t b B =max A 2O B t b A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB ; where 8 B 2P ;t b B = t B : .32 Thenthesmallestpossiblerearrivaltimeatpoint B ,suchthattherewill arrivefrompoint B totheperimeter P intime,isgiveninthefollowingdenition. Denition3.4.2 Foranypoint A ,theminimalarrivaltime A isdenedby A =max f t 0 A 0 )]TJ/F20 7.9701 Tf 18.02 14.944 Td [(n X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i j A 0 2P ; A 1 ;:::;A n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 2NnP ;A n = A; 0 n m b g ; where m b isthenumberofpointscontainedintheset F Thischoiceof t B guaranteesthatthereisnotgoingtopropagatetotheneighbors of B tooearly. Denition3.4.3 Let V b denoteasetofallvectorsin R m [fg ,where m isthe numberofpointscontainedintheset F .Letusdenoteby t k B theentryofthestate t k thatcorrespondstothepointB,where t k 2 V b isthestateofthealgorithmthat wascomputedduringthe k -thiteration. Denition3.4.4 Wewilldenoteby W b 2 V asetofvectors,s.t.forany u 2 W b u B = foranypointBthatisnotreachablefrom P Inthefollowingalgorithm,duringeachiteration,thetimeofignitionofallthe pointsonthemeshisbeingupdatedfromitsneighborsusingformula.32.Such constructionofthealgorithmisveryconvenientforparallelcomputing,sincemostof thecomputationscanbeperformedsimultaneously. 37

PAGE 50

Algorithm3.4.5BackwardPropagationoftheFire Givenaretheperimeter P oftherearea FM ,spreadrate t AB forall AB 2E ,and t 0 B 2 R forall B 2P .Initially t 0 B = forall B 2FnP Fork=1,2,... Forallpoints B 2FnP t k B =max A 2O B f t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB g .33 end end Lemma3.4.6 Algorithm.4.5denesamapping b : W b W b by b t k = t k +1 Proof: Weneedtoshowthatfor t k 2 W b ;t k +1 = b t k 2 W b .Usingthedenition of W b .4.4,itfollowsfromremark3.3.4and.33that t k +1 2 W b Wewillshowthatthemappingismonotonousinthepartialorderingon W b u v 8 B 2F : u B v B .34 forany u;v 2 W b Lemma3.4.7 Forany u;v 2 W b :if u v ,then u v : Proof: Let u = u k v k = v ,thenbydenitionforall A 2F u k A v k A Since b u k = u k +1 and b v k = v k +1 ,thenfrom.33,forall B 2FnP u k +1 B v k +1 B .Inaddition,forall B 2P u k +1 B = v k +1 B andthus u v : Lemma3.4.8 Themapping b issequentiallycontinuouson W b Proof: Supposethatforany A 2F t k 2 W b lim k !1 t k A = t A ; 38

PAGE 51

where t A 2 [ ; + 1 : Letusdenote b t k = u k ,thenitfollowsfrom.4.6that forany B 2FnP u k B =max A 2O B f t k A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB g ; where O B isaniteset.Then lim k !1 t k A = t A = lim k !1 t k A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB = t A )]TJ/F15 11.9552 Tf 11.956 0 Td [( t AB : Sincethemaximumistakenovertheniteset,then lim k !1 max A 2O B f t k A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB g =max A 2O B f t A + t AB g = = lim k !1 u k B = u B WewanttoexploretherelationbetweenAlgorithms3.3.7and3.4.5.Forthis purpose,letusdenetherelation rst. Denition3.4.9 Assumethat A;B 2 ,then t f B = t f A + t AB ; .35 where t f isasequencethatisbeingproducedafterapplyingAlgorithm3.3.7tothe initialsequence t 0 Intheorems3.4.10and3.4.11weassumethatAlgorithm3.3.7startsfromthe givenperimeter P 1 ,whichcanbeasingleignitionpoint,andreachesitsxedpoint t f = t f .Pickanarbitraryrearea F2M sothat P 1 2P 2 ,where P 2 isacontour of F ,anduse P 2 asaperimeterforAlgorithm3.4.5,meaningthatforany A 2P 2 t b A = t f A .AssumethatAlgorithm3.4.5hasreacheditsxedpoint b t b = t b Theorem3.4.10Algorithmcomparison Foranypoint A 2F ,ifthereexists apath f B 1 ;:::;B n g = 2P 1 ,suchthat B 0 ;B 1 2 ; B 1 ;B 2 2 ;:::; B n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ;B n 2 ;B 0 = A;B n 2P 2 ; 39

PAGE 52

ab Figure3.6:aThesituationwhenbothforwardandbackwardpropagationsgive thesameresults.bSincetherearenooutgoingarrowsfromthepoint C ,thevalue oftherearrivaltimeatthispointwilldierforforwardandbackwardpropagations. then t b A = t f A Proof: Byassumptionwearegiventhat t f B n = t b B n .From.35itfollows that t f B n = t f B n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 + t B n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 B n = t f B n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = t f B n )]TJ/F15 11.9552 Tf 11.955 0 Td [( t B n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 B n ; .36 thenfrom.31 t f B n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 max A 2O B n t A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB n : .37 Itfollowsfrom.36and.37that t f B n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = t f B n )]TJ/F15 11.9552 Tf 11.955 0 Td [( t B n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 B n =max A 2O B n t A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB n .38 andthus t f B n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 = t b B n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 : .39 Usingthesamelogicitfollowsbyinductionon i that t f B i = t b B i ; 8 i =0 ;:::;n Therefore t f A = t b A 40

PAGE 53

Theorem3.4.11GeneralAlgorithmComparison Forany A 2F ,ifthere existsapoint B ,suchthat t f B = t f A + t AB ; .40 then t b = t f : Proof: Bydenitionequation3.40meansthat A;B 2 .Since F canhave onlylimitedamountofpointsthenthereisapath B 1 ;:::;B n A;B 1 2 ; B 1 ;B 2 2 ;:::; B n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;B n 2 ;B n 2P 2 ; Andthusbytheorem3.4.10, t b A = t f A forany A 2F Thenextlemmashows,thatthexedpointofthemapping b on W b ifitexists isunique. Lemma3.4.12 If t = b t t 2 W b ,thenforany A from F t A isthemaximal arrivaltimeatthepoint A Proof: Foreverypoint A 2F ,denote L A thesmallestlength n ofthepath forwhichthemaximumisachievedinthedenition3.4.2ofthearrivaltimeofA. Theproofwillproceedbyinductionon n .Let n =0,thenallthepoints A forwhich L A =0arelocatedin P andsoitfollowsfromdef.3.4.2that A = t 0 A : For thecasewhen n =1,let A 2N ,s.t. L A =1,then A =max A 0 t A 0 )]TJ/F17 7.9701 Tf 18.472 14.944 Td [(1 X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A 1 = A = =max A 0 f t A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 A 1 ;A 0 2P ;A 1 = A g = t A : Supposethatthestatementholdsforallpoints A ,suchthat L A = k thatis, t A = A =max A 0 ;:::;A k )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 t A 0 )]TJ/F20 7.9701 Tf 18.279 14.944 Td [(k X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A k = A 41

PAGE 54

For n = k +1let A 2N ,suchthat L A = k +1, A =max A 0 ;:::;A k t A 0 )]TJ/F20 7.9701 Tf 12.869 14.944 Td [(k +1 X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A k +1 = A ; where A k canbeonlytakenfromthesetofneighborsof A ,suchthat L A k = k hence A =max A 0 ;:::;A k t A 0 )]TJ/F20 7.9701 Tf 18.278 14.944 Td [(k X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i )]TJ/F15 11.9552 Tf 11.956 0 Td [( t A k A k +1 ;A 0 2P ;A k +1 = A;L A k = k : A =max A k A 2E f A k )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A k A g =max A k A 2E f t A k )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A k A g = t A : Inthetheorembelowwewanttoprovethatmapping b hasauniquexedpoint. Theorem3.4.13 Forany t 0 2 W b ,thesequence f t k g ,denedby t k = b t k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 convergestotheuniquexedpointofthemapping on W b Proof: Letusrecallthat t 0 B = 8 > > < > > : t 0 B < 1 ; 8 B 2P ; 8 B 2FnP .41 and t i = b t i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 : From.32,forany B 2F t 1 B t 0 B andthus t 1 t 0 : Fromthemonotonicityof b Lemma3.4.7,wehavebyinductionthatforall i = 1 ; 2 ;::: t i t i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 Ifthepoint B 2FnP isnotreachablefrom P thenforall i ,then t i B = : 42

PAGE 55

Incasewhenthepoint B isreachablefrom P ,then,sincesequence f t i B g is monotonicallyincreasingandboundedabovebymax A 2P f t 0 A g ,ithasalimit t B Consequently, lim i !1 t i = t and,since t i +1 = b t i andthemapping b issequentiallycontinuous,itfollowsthat t = b t .ItfollowsfromLemma.4.12thatthexedpointof b isunique,which completestheproof. Inparticular,thetheorembelowshowsthatforany t 0 2 W b ,suchthat 8 A 2 FnP t 0 A = ; thesequence f t k g ,denedby t k = b t k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,convergesinanite numberofsteps k ,where k m b Theorem3.4.14 Supposethat t 0 2 W b t k = b t k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 forall k 1 ,andforall A 2FnP t 0 A = : Then,foranypoint A 2F ,whichcanbereachedfrom P byapathwith k edges, t k A =max A 0 ;:::;A n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 t 0 A 0 )]TJ/F20 7.9701 Tf 18.02 14.944 Td [(n X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A 0 2P ;A n = A;n k .42 Inparticular, t k equalstotheuniquexedpointof b on W b forsome k m b Proof: Wewillshow.42byinduction. Let k =1,thenforany A 2F thatcanbereachedfrom P inonestep t 1 A =max A 0 2O A f t 0 A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 A g =max A 0 2P f t 0 A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 A g : Suppose.42holdsfor k andsoweneedproveitfor k +1.Bydenitionof b t k +1 A =max B 2O A f t k B )]TJ/F15 11.9552 Tf 11.955 0 Td [( t BA g : 43

PAGE 56

Substituting.42for t k B weget t k +1 A =max B 2FnP 8 > > < > > : max 8 > > < > > : t 0 A 0 )]TJ/F20 7.9701 Tf 18.021 14.944 Td [(n X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ;A n = B; A 0 2P ;A 1 :::;A n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 2FnP ;n k 9 > > = > > ; )]TJ/F15 11.9552 Tf 11.955 0 Td [( t BA 9 > > = > > ; =max 8 > > < > > : t 0 A 0 )]TJ/F20 7.9701 Tf 12.61 14.944 Td [(n +1 X i =1 t A i )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 A i ; A 0 2P ;A 1 :::;A n 2FnP ;A n +1 = A;n +1 k +1 9 > > = > > ; : 3.4.2FastBackwardPropagationAlgorithm ThemainfeatureoftheFastBackwardPropagationAlgorithmisthatitonly usesthepoints,whichtimeofignitionwaschangedrecentlytoupdatethevaluesof timeofignitionoftheirneighbors.Thismethodisecientintermsofspeed,saving memoryanddecreasingtheamountofiterations,howevertheconstructionofthe algorithmmakesithardtoimplementforaparallelcomputing. Algorithm3.4.15FastBackwardPropagationoftheFire Givenarerearea FM ,itsperimeter PF ,andtheignitiontimes t 0 B = T forall B 2P 1.Initializetheauxiliaryset D 0 = P .Forallpoints A= 2P ,set t 0 A = 2.For k =1 ; 2 ;::: 3.Initializethesetofpointsthatwereupdatedinthiscycle, D k = ; 4.Forall B f b B := t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 B : 5.Forall A 2D k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 forallneighbors B of A if t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB >f b B then .43 f b B := t k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB ; .44 D k = D k [f B g : .45 44

PAGE 57

6.Forall B t k B = g b B : 7.If D k 6 = ; Repeatfromstep2. else D k = ; thatis, t hasnotchangedinstep5, EXIT Lemma3.4.16 Thealgorithmdenesamapping b on W b ,by b t k = t k +1 is monotonicallyincreasinganditsrangeisin W b Proof: Asitfollowsfromtheequations.43and3.44,foreachentry B ofthe state t k ,thevalueof t k +1 B canonlyincreaseorstayunchanged,whichproofsthe monotonicincreaseof b Inordertoshowthattherangeof b isin W b ,weneedtoprovethatforall B notreachablefrom P t k B = t k +1 B = ,whichfollowsfromtheremark3.3.4 and.43,3.44. Theorem3.4.17 Thesequence t k denedbyAlgorithm3.4.15converges. Proof: Since b isamonotonicallyincreasingmapping,itfollowsthatforany A 2F t k A ismonotonicallyincreasingwith k .Since t k A isalsoboundedabove bymax B 2P f t 0 B g ,thesequenceconverges. Denition3.4.18 Foreveryiteration k oftheAlgorithm3.4.15theset U b;k isdened insuchway: 1. U b; 0 = P ; 2.If D k 6 = ; :Finda B k ,s.t. t k B k =max f t B j B 2NnU b;k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 g .46 U b;k = U b;k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 [f B k g ; 45

PAGE 58

3.If D k = ; : U b;k = N : Theorem3.4.19 Algorithm3.4.15isnite. Proof: InthefollowingLemma.4.20wewillshowthat U l isasetthatonly consistsofpermanentpoints.3.23atthestep l .Accordingtothestep3ofthe denition3.4.18,thesetofpermanentpointsincreasesatleastbyonepointateach step.Assuch,thealgorithmwillbenitesincethesizeofthemeshisnite. Lemma3.4.20 8 n 8 k>n forany B 2U b;n : B= 2D k Proof: Theproofisbyinductionon n : 1.For n =0,initially U b; 0 = P .Sincethetimeofignitionofthepointsonthe perimeterissetandcannotbeupdatedduringthealgorithm,thusnopoint B from P canbein D k forany k> 0. 2.Supposethatthestatementholdsforallthecyclesupto n )]TJ/F15 11.9552 Tf 11.018 0 Td [(1.Fromdenition 3.4.18,aftertheendofcycle n B n 2 argmax f t n A j A 2FnU b;n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 g ; .47 and U b;n = U b;n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 [f B n g Bytheinductionassumption, P ;B 1 ;:::;B n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = 2D k forall k>n )]TJ/F15 11.9552 Tf 12.223 0 Td [(1,andso, theycannotbeusedtoupdatethevalue t atthepoint B n atanycycle k>n Let A 2FnU b;n = FnfP ;B 1 ;:::;B n g .Wewanttoshowthat t i A t n B n forall i>n ,and,thus, A cannotbeusedtoupdatepoint B n inanycycle i>n either,sinceitwillnotsatisfytheinequality.43. aIf A= 2D i forall i>n thatis,thepoint A wasneverupdated,and t i A = t n A t n B n by.47. 46

PAGE 59

bAssumethat A 2 D i forsome i>n ,andsousingformula.44, A here A = A i waspreviouslyupdatedfromsomepoint A i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 2D i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 whichwasupdatedfromsome A i )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 2 D i )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 ; e.t.c.,untilsome A n +1 2 D n +1 wasupdatedfromsome A n 2 D n .Then, t i A i t i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 A i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 t n A n t n B n ; because t n B n wasthemaximalfrom.47. Hence, t i A couldnotbeusedtoupdate t at B n .Since A wasarbitraryfrom FnU b;n ,therefore, B n wasneverupdatedinacycle k>n thatis, B n = 2D k for all k>n Theorem3.4.21 Algorithm3.4.15generatesvaluesof t whichsatisfy.32forall pointsin N Proof: LetsassumethatAlgorithm3.4.15isnishedatstep i ,butthereisa point B and A 2O B ,suchthat t i A )]TJ/F15 11.9552 Tf 11.956 0 Td [( t AB >t i B .48 SincetheAlgorithmisnisheditfollowsfromstep4ofAlgorithm3.4.15andstep3 ofthedenition3.4.18that D i = ; and U i = F Sincethereisastronginequalityin.48,then t i A > andthus 9 j =min f k : A 2 D k ;k
PAGE 60

Theorem3.4.22 Supposethat t 0 on P and t 0 A = forallthepoints A 2FnP ThenAlgorithm3.4.5andAlgorithm3.4.15producethesamesequenceofstates. Proof: Denesequence v k byAlgorithm3.4.5, v k = b v k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 andsequence u k byAlgorithm3.4.15, u k = b u k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,sothat u 0 = v 0 = t 0 .Inordertoprovethe theorem,weneedtoshowthat v k = u k forany k .Theproofwillproceedbyinduction on k 1.For k =0theprooffollowsfromthedenition: u 0 = v 0 2.Supposethat v k = u k ,thatis, 8 B 2F : v k B = u k B 3.Tonishtheproofweneedtoshowthat v k +1 = u k +1 Assumethatthereexistsapoint B ,suchthat v k +1 B 6 = u k +1 B .Accordingto .33inAlgorithm3.4.5, v k +1 B =max A 2O B f v k A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB g = v k A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 B ; .50 forsome A 0 2O .InAlgorithm3.4.15,thevalueof u k +1 B canonlybeupdatedto itsnalvaluein.44fromoneoftheneighbors A 00 ofthepoint B ,andso u k +1 B = u k A 00 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 00 B = v k A 00 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 00 B max A 2O B f v k A )]TJ/F15 11.9552 Tf 11.955 0 Td [( t AB g = = v k A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 B = v k +1 B Sincebyassumption v k +1 B 6 = u k +1 B ,then u k +1 B
PAGE 61

Butthen,since A 0 2O B and j k u k +1 B : 4 : 16 u j +1 B : 43 ; 3 : 44 u j A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 B : 52 = : 52 = u k A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 B = v k A 0 )]TJ/F15 11.9552 Tf 11.955 0 Td [( t A 0 B : 21 = v k +1 B ; whichcontradicts.51 2.Otherwise,assumethat A 0 = 2D i forall i
PAGE 62

3.5TimeDependentMethod 3.5.1BackwardPropagation Theadvantageofthemethoddescribedinthissectionisthatitusestherateof spreadofthereasatimedependentvariable.Thismakesthismethodapplicable intherealworldproblems,wheresuchvariablesaswindandmoisturearechanging continuously. Inthegure3.7,itisshownhowtherepropagatesuntiltimestep t k .There hasspreadfrompoint B topoint C onthewaytopoint A andcoveredthedistance d .Thedistance d A;B thattherecoversonthewayfrompoint B topoint A at thetime t ,giventherateofspreadofthere ROS A;B;t canbedescribedbythe dierentialequation @d A;B @t = ROS A;B;t .58 Inordertosolvethedierentialequation,weareusingEuler'sdiscretizingmethod. Accordingtogure3.7,equation.58canbewrittenintheintegralform Z t B t A ROS A;B; d = d A;B : .59 Inotherwordstheproblemthatequation.59issolvingistondhowmuchtime t B ittakesfortheretocoverthedistance d A;B betweenpoints A and B and ignitepoint B ,giventhatpoint A wasignitedattime t A Algorithm3.5.1Time-dependentBackwardPropagationoftheFire Given arerearea FM ,itsperimeter PF ,andtheignitiontimes t 0 B = T forall B 2P .Forany A;B 2E andtimestep k thedistancebetweenpointsAandB Dist A;B andtheRateofSpread RoS k A;B m/secisgiven,wherethetimestep lengthis TS seconds. 50

PAGE 63

Figure3.7:Firelineatstep t k ,wheretherecovereddistance d onthewayfrom point B topoint A d 0 = ROS t;C; ~ BA: 1.Initializetheauxiliaryset D 0 = P .Forallpoints A= 2P ,set t 0 A = .For anypoints A and B ,s.t. AB 2E ,initializethetimethatittakesforthereto travelfrompoint A to B as A;B =0 2.For k =1 ; 2 ;::: 3.Initializethesetofpointsthatwouldbeupdatedintheendofthecurrentcycle, D k = ; andthetimethatwouldbeleftfortheretopropagatefrompoint A to point B duringthecurrenttimestep, ts A;B = TS 4.Forall B u B := t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 B : 5.Forall A 2D k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 hereset D k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mightstillgetupdateddynamically,wherenew pointsareaddedintheendoftheset forall B 2O A If dist A;B RoS i A;B >ts A;B 51

PAGE 64

then casewhenitwouldtakemoretimestepsfortheretotravel frompoint A topoint B A;B = A;B + ts A;B ; Dist A;B = Dist A;B )]TJ/F19 11.9552 Tf 11.955 0 Td [(RoS i A;B ts A;B ; D k = D k [ A; else casewhentherereachespoint B duringthecurrenttimestep A;B = A;B + Dist A;B RoS i A;B If u B
PAGE 65

Repeatfromstep2. else D k = ; thatis,forany A t A cannotchangeanymore. EXIT 3.5.2ForwardPropagation Algorithm3.5.2Time-dependentBackwardPropagationoftheFire Given arerearea FM ,itsperimeter PF ,andtheignitiontimes t 0 B = T forall B 2P .Forany A;B 2E andtimestep k thedistancebetweenpointsAandB Dist A;B andtheRateofSpread RoS k A;B m/secisgiven,wherethetimestep lengthis TS seconds. 1.Initializetheauxiliaryset D 0 = P .Forallpoints A= 2P ,set t 0 A = .For anypoints A and B ,s.t. AB 2E ,initializethetimethatittakesforthereto travelfrompoint A to B as A;B =0 2.For k =1 ; 2 ;::: 3.Initializethesetofpointsthatwouldbeupdatedintheendofthecurrentcycle, D k = ; andthetimethatwouldbeleftfortheretopropagatefrompoint A to point B duringthecurrenttimestep, ts A;B = TS 4.Forall B u B := t k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 B : 5.Forall A 2D k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 hereset D k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mightstillgetupdateddynamically,wherenew pointsareaddedintheendoftheset forall B 2O A If dist A;B RoS i A;B >ts A;B 53

PAGE 66

then casewhenitwouldtakemoretimestepsfortheretotravel frompoint A topoint B A;B = A;B + ts A;B ; Dist A;B = Dist A;B + RoS i A;B ts A;B ; D k = D k [ A; else casewhentherereachespoint B duringthecurrenttimestep A;B = A;B + Dist A;B RoS i A;B If u B >u A + A;B u B := u A + A;B end 8 C 2O B ;ts B;C = ts B;C )]TJ/F19 11.9552 Tf 15.85 8.088 Td [(dist A;B RoS i A;B : D k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = D k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 [ B endendofstep5 endendofstep4 D k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 = D k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 nf A g endendofstep2 6.If D k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 6 = ; Repeatfromstep5. 7.Forall B t k B = u B : 8.If D k 6 = ; 54

PAGE 67

Repeatfromstep2. else D k = ; thatis,forany A t A cannotchangeanymore. EXIT 55

PAGE 68

4.ApplicationtoFires:PerimeterIgnition 4.1InitializationfromaFirePerimeter ThedescriptionoftheWRF-SFIREmodelisfrom[20],[21],theperimeterignition isafurtherdevelopmentoftheideasin[17]andsomeoftheresultswerealready publishedin[19]. Inthischapterweuseaschemeforcreatinganarticialrehistory,thatwillbe usedintherereplayscheme,andtestitonarealcasesimulationofthetwores, WitchandGuejito,thathavehappenedinSantaAnain2007.Givenareperimeter,Algorithm3.5.2isusedtoapproximateignitiontimes,representedas tign i;j andwhicharelocatedatthemeshpoints.Theapproximationisestablishedbysimulatedpropagationbasedontheirrepropagationspeedandignitiontimesofthe neighboringmeshpoints. Areperimeter,representedas P ,isaclosedcurvecomposedoflinearsegments. Itisgivenasasequenceofthecoordinatesattheendpointsofthesegments.In practice,suchgeospatialdataareoftenprovidedasaGISshapele,orencodedina KMLle,e.g.,fromGEOMAC. Theignitiontimesatlocationsoutsideofthegivenrecontourcanbethoughtof aspredictionsoffutureignitiontimesinthoselocationsastherecontinuestoburn. Intherealcase,thewindandthespeedofpropagationalwayschangewithtime, andsotheywillbetreatedasvariablesinsteadofconstants.Forthisreason,theFast Marchingmethod,whichrequiresthepropagationspeedconstantintime,cannotbe used. 4.2CreatingArticialIgnitionTimeHistoryfromtheCurrentFire Perimeter Atypicalremodelstartsaresimulationfromaknownignitionpointataknown ignitiontime.However,usersarealsointerestedinstartingWRF-SFIREfroman existingre,whichpresencehasbeendetectedandmapped.Underthesecircumstances,theignitionpointandignitiontimetypicallybecomeknowntoolatetobe 56

PAGE 69

relevantforreal-timesimulationandforecasting.Thus,weareinterestedinstarting aresimulationfromagivenreperimeteratagiventime,fromnowon,calledthe perimetertime .However,thefuelbalanceandthestateoftheatmospheredepend onthehistoryofthere,whichisnotknown. Oursolutionistocreateanapproximatearticialhistoryoftherebasedon thegivenreperimeterandtheperimetertime,thefuelmap,andthestateofthe atmosphereduringtheperiodbeforetheperimetertime.Thehistoryisencodedas therearrivaltimeatthenodesoftheremodelmesh.Wethenusethearticial rearrivaltimeinsteadoftherespreadmodeltoburnthefuelandgeneratethe heatreleasetotheatmosphere.Replayingthearticialrehistoryenablesgradual fuelburn,insteadofignitingthewholeinsideofthereperimeteratonce,andthus allowsthere-inducedatmosphericcirculationtodevelop.Attheperimetertime, thecompletecoupledatmosphere-remodeltakesover. 4.3EncodingandReplayingtheFireHistory Thestateoftheremodelconsistsofalevelsetfunction,,givenbyitsvalues onthenodesoftheremodelmesh,andtimeofignition T i .Thelevelsetfunctionis interpolatedlinearly.Atagivensimulationtime t ,thereareaisthesetofallpoints x;y where t;x;y 0.Thelevelsetfunctionandtheignitiontimesatisfythe consistencycondition t;x;y 0 T i x;y t; .1 asbothoftheseinequalitiesexpresstheconditionthatthelocation x;y isburning atthetime t .Ineverytimestepofthesimulation,thelevelsetfunctionisadvanced byonestepofaRunge-Kuttaschemeforthelevelsetequation d dt = )]TJ/F19 11.9552 Tf 9.299 0 Td [(R kr k ; where R = R t;x;y isthererateofspread,whichdependsonthefuel,windspeed, andslope.Theignitiontimeatnodesisthencomputedforallnewlyignitednodes, anditsatisestheconsistencycondition.1. 57

PAGE 70

Therehistoryisencodedasanarrayofignitiontimes T i x;y ,prescribedatall remeshnodes.Toreplaythereintheperiod0 t T per ,thenumericalscheme foradvancingand T i issuspended,andinsteadthelevelsetfunctionissetto t;x;y = T i x;y )]TJ/F19 11.9552 Tf 11.955 0 Td [(t: Aftertheendofthereplayisreached,thenumericalschemeofthelevelsetmethod isstartedfromthelevelsetfunctionat t = T per Forreasonsofnumericalaccuracyandstability,thelevelsetfunctionneedsto haveapproximatelyuniformslope.Forexample,averygoodlevelsetfunction,which hasslopeequaltoone,isthesigneddistancefromagivenclosedcurve, x;y = dist x;y ; \051 ; wherethesignistakentobenegativeinsidetheregionlimitedby,andpositive outside[31].Thus,theignitiontimes T i needtobegivenonthewholedomainand theyneedtobesuchthat T i decreaseswiththedistancefromthegivenperimeter insidethereregion,andincreasesoutside.Theignitiontimes T i outsideofthe givenreperimeterareperhapsbestthoughtofaswhattheignitiontimesmightbe infutureastherekeepsburning. 4.4Results 4.4.1SantaAnaFires Thissubsectionwasalreadypublishedasapartof[19].Theseweretwores, WitchreandthenlaterGuejitore,whichmergedquicklyintoonemassivere. TheperimeterfromthesimulationonOctober22,2007,1:00PMPDTisinFig.4.2, andthearticialrearrivaltime,createdbasedontheprecomputedreprogression, isshowninFig.4.3.Thearticialrearrivaltimegraphhastwominima,which correspondtothetwoignitionpointsandtimes.FortheWitchre,theerrorinthe ignitionpointlocationwas3.28km,whichis5.7%ofthediameterofthegivenre perimeter,andtheignitiontimewasexactlythesame.FortheGuejitore,theerror 58

PAGE 71

Figure4.1: a Propagationofignitiontime t toanodefromneighboringnodes alreadyonre. b Backtrackingpropagationbackintimeofignitiontimeto anodefromneighboringnodeswheretherearrivedlater.Reproducedfrom[19]. inthelocationoftheignitionpointwas0.04km,whichis0.07%ofthediameterof theperimeter,andtheerrorintheignitiontimewas0.26h,whichis2 : 4%ofthetime fromtheignitiontotheperimetertime.TheRMSEofthearticialrearrivaltime uptotheperimetertimecomparedtotheoriginalsimulationwas1,199s.Scaling bythetime24h15m=81 ; 100sfromtherstignition,October21,200712:15PM PDTtothereperimetertimeOctober22,2007,1:00PM,givestherelativeRMSE ofthearticialrearrivaltimeonly1.5%.Figure4.4showsacomparisonofthe windfromtheoriginalsimulationandfromthespin-upusingthearticialrearrival time.Wehavethencontinuedthesimulationforadditional8htoassesstheeect oftheperimeterignitiononfurtherpropagationofthereFig.4.5.Again,the originalsimulation,andthesimulationstartedfromtheperimeterignition,arequite close,demonstratingtheutilityofthepresentapproachtosimulatingtheprogression ofalreadydevelopedresdetectedasperimeters,ratherthanignitionpoints.The RMSEoftherearrivaltimeaftercontinuingfromthearticialrearrivaltimefor 8hwas706sthatis,0 : 25%.Thisistheerroroftheperimeterignition,whichwas entirelycausedbytheslightchangeinthewindattheperimetertimeduetotheuse ofthearticialrearrivaltimeinsidethegivenperimeter. 59

PAGE 72

Figure4.2:Perimeterofthe2007SantaAnaressimulationOctober22,2007 1PMPDT[19].Thereconsistedoftwores,WitchandGuejito,whichstartedon October21,200712:15PMPDTand22October20071:00AMPDT,respectively, andsubsequentlymerged.Theasterisksandcirclesfromlefttorightindicatethe realandarticiallycalculatedignitionpointsofGuejitoandWitchresrespectively. Reproducedfrom[19]. 60

PAGE 73

Figure4.3:Articialrearrivaltimefoundbyrepropagationbackintimefromthe reperimeterin4.2.Thetwopeaksonthebottom,markedbyarrows,arethetwo ignitionlocationsandtimes,foundautomaticallyfromtheperimeter.Thevertical axisandthefalsecolorarethetimefromthebeginningofthesimulation.Reproduced from[19]. 61

PAGE 74

Figure4.4: a Horizontalwindat6.1minthe2007SantaAnaressimulation onOctober20071:00PMPDT. b Thesamewindasin a ,butwiththearticial ignitiontimehistoryfromFig.4.3untilOctober20071:00PMPDT. c Thedierence ofaandb.TheRMSEis1.1 ms )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ,whichis8.8%ofthemaximalwindspeed12.53 ms )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 .Reproducedfrom[19]. 62

PAGE 75

Figure4.5: a Fireperimeterinthe2007SantaAnaressimulationon22October 22,20079PMPDT. b Thesameperimeterasin a ,butwiththearticialignition timehistoryfromsimulationdataFig.4.3onOctober22,2007,1PMPDT.The dierencesinthesimulation8hourslaterareonlyminor,suchastheprotuberance atthenortheastpartoftheperimeter.Reproducedfrom[19]. 4.4.2IdealCase.AlgorithmDrivenbyPureAtmosphericDatawithno FireInvolved ThesimulationoftheSantaAnaresdescribedintheprevioussectionutilized previouslysimulatedwindpriortothedesignofExtendedFastBackwardalgorithm Algorithm3.5.2.Suchapproachusestherateofspreadcomputedbeforehand, whichisbasedontheknownignitionpointsandthere-atmospherefeedback,which modiesthewinds,whichinturnaectthespreadrate.However,inreality,the ignitionpointtostartthesimulationfromisnotknownyet.Inthissection,we studyhowthealgorithmperformsusingwindsthathavenotbeenperturbedbythe presenceofre. Thereperimeterisobtainedfromacoupledatmosphere-resimulation,andit isusedtoinitializetheExtendedFastBackwardalgorithm,whichgoesbackintime 63

PAGE 76

fromtheperimeter.Therateofspreadiscomputedfromwindsunperturbedbythe re,usinganidenticalsimulationwheretherewasnotignited. InFigure4.6a,therestartsfromtwoignitionlinesoriginatingat1860mEast, 1860mNorth,andtheignitioncontinuesinoppositedirections.Theignitionpoint correspondsto i =31, j =31ontheatmosphericmesh,and i f =310, j f =310on theregrid.Figure4.6bpresentsthereperimeter,measuredafter30minutes ofredrivensimulation.Figures4.7aand4.7bshowthearticialtimeofignition,createdafterapplyingtheextendedbacktrackingalgorithmtothereperimeter measuredat30minutesofthe nofire and firedriven simulationrespectively,with theresultingignitionpointslocatedat i f =312 ;j f =307and i f =315 ;j f =307. ThetimeofignitionhistoryoftheoriginalresimulationisshowninFigure4.8a. Thedierencebetweenrearrivaltimescalculatedusingthe nofire andoriginal simulationisshowninFigure4.8b.Figure4.9showsthegraphicalcomparisonof thelocationoftherealignitionpoint,theonefoundwithperturbedwinds,andthe ignitionpointwithwindswithoutreinrelationtothecontouroftheperimeter. Overall,theresultsofusingthererateofspreaddata,notaectedbythere, inExtendedFastBackwardpropagationalgorithmfortheidealcaseareclosetothe resultsbasedontheredrivendata. 64

PAGE 77

ab Figure4.6:aTheignitionpointoftheredrivensimulation.bPerimeterofthe re,takenaftertheredrivensimulationwasrunningfor30minutes.Thefalsecolor representstheamountoffuelburnt.ProblemsetupandvisualizationdonebyAdam Kochanski. ab Figure4.7:Articialrearrivaltimefoundbythebackwardrepropagationalgorithmwhichoriginatedfromthereperimeterin4.6bandwasusingnoredriven rateofspreadinaandredrivenrateofspreadinb.Theverticalaxisandthe falsecolorarethetimefromthebeginningofthesimulation. 65

PAGE 78

ab Figure4.8:Firearrivaltimeoftheoriginalsimulation.bDierencebetweenre arrivaltimeoftheoriginalsimulation4.8aandonecomputedbythebackwardre propagationalgorithmstartingfromtheperimeterandusingwindsnotaectedby thereFigure4.7a. Figure4.9:Locationoftherealignitionpointredcircle,theonefoundwith perturbedwindsbluecircle,andtheignitionpointwithwindswithoutreblack circleinrelationtothecontouroftheperimeter. 66

PAGE 79

5.FastFourierTransformEnsembleKalmanFilterwithApplicationtoa CoupledAtmosphere-WildlandFireModel Inthischapter,basedon[27],weproposeanewtypeoftheEnsembleKalman FilterEnKF,whichusestheFastFourierTransformFFTforcovarianceestimation fromaverysmallensemblewithautomatictapering,andforafastcomputationof theanalysisensemblebyconvolution,avoidingtheneedtosolveasparsesystemwith thetaperedmatrix.ThemethodiscombinedwiththemorphingEnKFtoenable thecorrectionofpositionerrors,inadditiontoamplitudeerrors,anddemonstrated onWRF-Fire,theWeatherResearchForecastingWRFmodelcoupledwithare spreadmodelimplementedbythelevelsetmethod.Mypersonalcontributionwas visualizationofthecomputationalresultsandparticipatinginthediscussionsofthe theoreticalbaseofthechapter. Dataassimilationisastatisticaltechniqueusedtomodifythestateofarunning modelinresponsetodata,basedonsequentialBayesianestimation[18].TheEnKF [13]accessesthemodelonlyasablackbox,whichmakesitsuitableforawiderange ofproblems.However,theensemblesizeneededcanbelarge,andtheamountof computationrequiredinEnKFcanbesignicantwhentheEnKFismodiedto suppressspuriouslong-rangecorrelations.WeproposeanewvariantofEnKFthat canovercomethesedicultiesbytheuseofFFT.Thenewmethodisappliedtothe morphingEnKF[4].Mypersonalcontributionwasvisualizationofthecomputational resultsandparticipatinginthediscussionsofthetheoreticalbaseofthechapter. 5.1DataAssimilation Werstprovideabackgroundinformationaboutdataassimilation. TheEnKFadvancesintimeanensembleofsimulations u 1 ;:::;u N ,whichapproximatestheprobabilitydistributionofthemodelstate u .Thesimulationsarethen advancedintimeuntil analysistime ,whennewdata d arrives.Itisassumedthatthe dataerrorisknown, d )]TJ/F19 11.9552 Tf 10.984 0 Td [(Hu N ;R given u ,where H is observationoperator and 67

PAGE 80

R isthe dataerrorcovariancematrix .Theensemble,nowcalled forecastensemble iscombinedwiththedatatogivethe analysisensemble bytheEnKFformulas[5] u a k = u k + C N H T )]TJ/F19 11.9552 Tf 5.48 -9.684 Td [(HC N H T + R )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 d + e k )]TJ/F19 11.9552 Tf 11.956 0 Td [(Hu f k ; .1 where C N isanestimateofthecovarianceofthemodelstate,and e k israndom perturbation e k N ;R .Theanalysisensemble u a 1 ;:::;u a N isthenusedasthe initialconditionforanewsimulation,advancedtoanewanalysistime,andthe analysiscycle repeats. InthestandardEnKF[5], C N isthesamplecovariancecomputedfromtheensemble.Itcanbeproved,undercertainassumptions,thattheensembleconvergesfor large N toasamplefromtheKalmanlteringdistributionand C N convergestothe truecovariance[28]. 5.1.1FFTEnKFandCovarianceEstimationbyFFT Startingfromthissection,thechaptercontainsmostlynewmaterial. Weareinterestedinobtainingareasonableapproximationofthecovariancematrixfromaverysmallsample.Therefore,wetakeadvantageofthefactthatthe simulationstate u isablockvector,wheretheblocksarevaluesofthemodelledphysicaleldsongridsofpointsinaspatialdomain,whicharediscreteversionsof smoothrandomfunctions,i.e.,realizationsofrandomelds.Butforasmallsample, theensemblecovarianceisamatrixoflowrankwithlargeo-diagonalelementseven atagreatdistance.Therefore,localizationtechniquesareused,suchastapering, whichconsistsofmultiplicationofthetermsofthesamplecovariancebyaxedfunctiontoforcethedrop-oofthecovarianceawayfromthediagonal,resultingina moreaccurateapproximationofcovarianceforsmallsamples[15].However,solving asystemwiththeresultingapproximatecovariancematrixisexpensive,becauseecientdenselinearalgebra,whichreliesontherepresentationofthesamplecovariance matrixastheproductoftworectangularmatrices[23],cannolongerbeused. 68

PAGE 81

Forsimplicity,weexplaintheFFTEnKFinthe1Dcase.Higher-dimensional casesworkexactlythesame.Considerrstthecasewhenthemodelstateconsistsof oneblockonly. ThebasicoperationintheEnKF.1isthemultiplication v = C N u ofavector u byanapproximatecovariancematrix C N .Denoteby u x i theentryofvector u ,correspondingtonode x i andsupposeforthemomentthattherandomeldis stationarythatis,itscovariancematrixsatises C x i ;x j = c x i )]TJ/F19 11.9552 Tf 11.955 0 Td [(x j forsome covariancefunction c .Then v istheconvolution v x i = X j C x i ;x j u x j = X j u x j c x i )]TJ/F19 11.9552 Tf 11.955 0 Td [(x j : ThediscreteFouriertransformchangesconvolutiontomultiplicationentrybyentry.Hence,iftherandomeldisstationary,multiplicationbyitscovariancematrix becomesmultiplicationbyadiagonalmatrixinthefrequencydomain. Theproposedmethodofcovarianceestimationconsistsofcomputingthesample covarianceoftheensembleinthefrequencydomain,andneglectingallofitsodiagonalterms.Thisisjustiedbytheassumptionthatthecovariancedepends mainlyondistance. 1.Givenensemble[ u k ],applyaFFToperator F toeachmembertoobtainthe member b u k = Fu k inthefrequencydomain. 2.Computetheapproximateforecastcovariancematrix b C N inthefrequencydomainasthediagonalmatrixwiththediagonalentries b c i equaltothediagonal entriesofthesamplecovarianceoftheensemble[ b u k ], b c i = 1 N )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 N X k =1 b u ik )]TJETq1 0 0 1 335.877 173.149 cm[]0 d 0 J 0.478 w 0 0 m 6.662 0 l SQBT/F25 11.9552 Tf 336.213 162.841 Td [(b u i 2 ; b u i = 1 N N X k =1 b u ik : .2 Multiplicationbytheapproximatecovariancematrix C N thenbecomesinthe frequencydomain u = C N v b u = Fu; b v = b c b u;v = F )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 b v; 69

PAGE 82

where isentry-by-entrymultiplication, b c b u i = b c i b u i .Intheimportantcase H = I and R = rI thewholestateisobservedandthedataerrorsareuncorrelatedand thesameateverypoint,consideredhere,theEnKF.1inthefrequencydomain reducestoentry-by-entryoperations, b u a k = b u k + b c b c + r )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 b d + b e k )]TJ/F25 11.9552 Tf 12.291 0 Td [(b u f k : .3 Inanapplication,thestatehasmultiplevariables.Thestatevector,itscovariance,andtheobservationmatrixthenhavetheblockform u = 2 6 6 6 6 4 u . u n 3 7 7 7 7 5 ;C = 2 6 6 6 6 4 C C M . . . . C M 1 C MM 3 7 7 7 7 5 ;H = H H M : .4 Assumethattherstvariableisobserved,then H = I H =0,..., H M =0. TheEnKF.1thensimpliesto u j ;a k = u j k + C j 1 N C N + R )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 d + e k )]TJ/F19 11.9552 Tf 11.956 0 Td [(u k ;j =1 ;:::;M; .5 whichbecomesinthefrequencydomain b u j ;a k = b u j k + b c j 1 )]TJ 5.328 -9.684 Td [(b c + r )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 b d + b e k )]TJ/F25 11.9552 Tf 12.291 0 Td [(b u k ; .6 wherethespectralcross-covariancebetweeneld j andeld1isapproximatedfrom b c j 1 i = 1 N )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 N X k =1 b u j ik )]TJETq1 0 0 1 286.145 236.421 cm[]0 d 0 J 0.478 w 0 0 m 6.662 0 l SQBT/F25 11.9552 Tf 286.48 226.113 Td [(b u j i b u ik )]TJETq1 0 0 1 357.374 236.421 cm[]0 d 0 J 0.478 w 0 0 m 6.662 0 l SQBT/F25 11.9552 Tf 357.709 226.113 Td [(b u i ; b u j i = 1 N N X k =1 b u j ik : .7 70

PAGE 83

5.1.2MorphingEnKF Totreatpositionerrorsinadditiontoamplitudeerrors,FFTEnKFiscombined withthemorphingEnKF[4,23].Themethodusesanadditionalensemblemember u N +1 ,calledthe referencemember .Givenaninitialstate u ,theinitialensembleis givenby u N +1 = u and u i k = u i N +1 + r i k I + T k ;k =1 ;:::;N; .8 where r i k arerandomsmoothfunctionson, T k arerandomsmoothmappings T k : ,and denotescomposition.Thus,theinitialensemblehasbothamplitude andpositionvariability,andthepositionchangeisthesameforallblocks.Random smoothfunctionsandmappingsaregeneratedbyFFTasaFourierserieswithrandom coecientsthatdecayquicklywithfrequency. Thedata d isanobservationof u ,anditisexpectedthatitdiersfromthe modelinamplitudeaswellasinthepositionofsignicantfeatures,suchasrelines. Therstblocksof u 1 ;:::;u N and d arethenregisteredagainsttherstblockofthe referencemember u N +1 .Wend registrationmappings T k : k =0 ;:::;N suchthat u k u N +1 I + T k ;T k 0 ; r T k 0 ;k =0 ;:::;N; where d = u 0 .Denetheregistrationresiduals r j k = u j k I + T k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 )]TJ/F19 11.9552 Tf 12.933 0 Td [(u j N +1 k =0 ;:::;N .The morphingtransform mapseachensemblemember u k intothe extendedstatevector u k 7! e u k = M u N +1 u k = T k ;r k ;:::;r M k : .9 Similarly,thedatabecomestheextendeddatavector d 7! e d = T 0 ;r 0 .The FFTEnKFmethod.6isappliedtothetransformedensemble e u 1 ;:::; e u N withthe 71

PAGE 84

observationoperatorgivenby )]TJ/F19 11.9552 Tf 5.48 -9.684 Td [(T;r ;:::;r M 7! )]TJ/F19 11.9552 Tf 5.479 -9.684 Td [(T;r .Thecross-covariances between x and y componentsof T and r areneglected,sothecovariance C in .5consistsofthreediagonalmatrices,and.6applies.Thenewtransformed referencememberisobtainedas e u a N +1 = 1 N P N k =1 e u a k .10 andtheanalysisensemble e u 1 ;:::; e u N +1 bythe inversemorphingtransform u a; i k = M )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 u N +1 e u a k = u i N +1 + r a; i k I + T a k ;k =1 ;:::;N +1 : .11 5.2ComputationalResults WehaveusedtheoptimizationmethodfromRef.[4]forregistration.Wehave usedtherealsineFFT,whichforceszerochangeontheboundary.Wehaveuseda standardidealproblemdistributedwithWRF-Fire.Themodelhasa420 420re meshanda42 42 41atmosphericmesh.Thefuelwasuniformonthewholedomain. Themodelwasinitializedwiththewindblowingdiagonallyacrossthegrid,andtwo lineignitionsandonecircleignitionoccurwithintherst4secondsofsimulation time.Afteroneminuteofsimulationtime,whentherewasestablishedandoneof thelinereshasmergedwiththecircularre,thesimulationwasstoppedandan initialensemblewasgeneratedbyrandomsmoothperturbationbothinpositionand inamplitude.Articialdatawascreatedbyasimilarperturbation.Theforecastwas takenthesameastheinitialensemble.Thedescribeddataassimilationalgorithmwas thenappliedwith5members,withtheresultsshowninFigure5.1forthemorphing EnKFandFigure5.2forthemorphingFFTEnKF.WeseethattheEnKFwasnot abletoapproachthatdataatallwithsuchasmallensemble,whiletheFFTEnKF deliveredanensemblearoundthecorrectdatashape. 5.3Conclusion WehaveshownthatthemorphingFFTEnKFiscapableofdataassimilationina wildresimulation,whichexhibitssharpboundariesandcoherentfeatures.Wehave 72

PAGE 85

shownthattheFFTEnKFcandeliveracceptableresultswithaverysmallensemble members,unlikethestandardEnKF,whichisknowntoworkwithmorphingfor thisapplication,butonlywithamuchlargerensemble[4]. 73

PAGE 86

aForecastbData cENKFanalysismember1dFFTKFanalysismember1 Reproducedfrom[27] Figure5.1:ThemorphingKalmanFilterEnKFwith5ensemblemembers,applied tothegroundheatuxfromtheWRF-Firemodel.Theensemblesizeisnotsucient, thecorrectanalysisisnotevenapproximatelyinthespanoftheforecast,andthe EnKFcannotreachit. 74

PAGE 87

aForecastbData cENKFanalysismember1dENKFanalysismember19 eFFTKFanalysismember1fFFTKFanalysismember19 Figure5.2:ThemorphingFFTEnKFwith5ensemblemembers,appliedtothe groundheatuxfromtheWRF-Firemodel.Theanalysisensemblemovedtowards thedata.Reproducedfrom[27]. 75

PAGE 88

6.ComputationoftheFuelFraction Thischapterisbasedontheresearchdonein[24].Mypersonalcontributiontothe chapterwasdevelopingthecodethatimplementsthecalculationofthefuelfraction andembeddingthecodeintotheWRFmodelcode.Thesectionbelowsummarizes thebackgroundmaterial. Initially,resimulationareaispartitionedintoagrid,whereeachlcellstartswith fuelfraction F =1.Inthischapterweareparticularlyinvestigatingthecasewhen thecellispartiallyburning.Oncethefuelisignitedatatime t i ,thefuelfraction decreasesexponentially, F t =exp )]TJ/F15 11.9552 Tf 10.494 8.088 Td [( t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t i T f ;t>t i ; .1 where t isthetime, t i istheignitiontime, F 0 istheinitialamountoffuel,and T f is thethenumberofsecondsforthefueltoburndownto1 =e 0 : 3689oftheoriginal quantity.Thefuelweight w isgivenbytheuserintheinputdataasoneofthe coecientsinthefuelcategories.ThedefaultvaluesaretakenfromtheCAWFE code,which,accordingto[7,p.55],werechosentoapproximatethemass-losscurve fromtheBURNUPalgorithm[1].Inthischapter,thespeedofburningistakento beindependentofthewindspeedandthefuelmoisture. Theaveragesensibleheatuxdensityreleasedintimeinterval t;t + t iscomputedas h = F t )]TJ/F19 11.9552 Tf 11.955 0 Td [(F t + t t 1 1+ M f w ` h; )]TJ/F15 11.9552 Tf 5.48 -9.683 Td [(Wm )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 .2 andtheaveragelatentheati.e.,moistureuxdensityisgivenby q = F t )]TJ/F19 11.9552 Tf 11.955 0 Td [(F t + t t M f + M f 1+ M f Lw ` ; )]TJ/F15 11.9552 Tf 5.479 -9.684 Td [(Wm )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 .3 where M f istheestimatedmassratioofthewateroutputfromthecombustionto thedryfuel,and L isthespeciclatentheatofcondensationofwaterat0 C,used fornominalconversionofmoisturetoheat.ThiscomputationisfromCAWFE. 76

PAGE 89

Itshouldbenotedthatthereissignicantuncertaintyinthedataaswellasin theapproximationsmadeabove,andmanyfactorsthatinuencethespreadrateare notaccountedfor. 6.1FuelFractionofthePartiallyBurningCell. Thissectioncontainsnewmaterial. Thefuelfractionisapproximatedovereachremeshcell C byintegrating.1 overthereregion.Hence,thefuelfractionremainingincell C attime t isgivenby F =1 )]TJ/F15 11.9552 Tf 31.12 8.088 Td [(1 area C ZZ x 2 C x ;t 0 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(exp )]TJ/F19 11.9552 Tf 10.494 8.088 Td [(t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t i x T f x d x : .4 Oncethefuelfractionisknown,theheatuxesarecomputedfrom.2and.3. Thisschemehastheadvantagethatthetotalheatreleasedintheatmosphereover timeisexact,regardlessofapproximationsinthecomputationoftheintegral.4. Ourobjectiveinthenumericalevaluationof.4isamethodthatissecondorder accuratewhenthewholecellisonre,exactwhennopartofthecell C isonre, andprovidesatransitionbetweenthesetwocases. Whilethefuelburntime T f canbeinterpolatedasconstantoverthewholecell, thelevelsetfunction andtheignitiontime t i mustbeinterpolatedmoreaccurately toallowasubmeshrepresentationoftheburningareaandagradualreleaseofthe heatastherelinemovesoverthecell.Wewillalsoneedthefuelfractioncomputed overeachmeshcell,becausetheheatuxesinthemeshcellsaresummeduptogive theheatuxinanatmosphericcell.Oursolutionistospliteachcellinto4subcells C j ,interpolatetothecornersofthesubcells,andaddtheintegrals, ZZ x 2 C x 0 1 )]TJ/F15 11.9552 Tf 11.291 0 Td [(exp )]TJ/F19 11.9552 Tf 10.494 8.088 Td [(t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t i x T f x d x = 4 X j =1 ZZ x 2 C j x 0 1 )]TJ/F15 11.9552 Tf 11.291 0 Td [(exp )]TJ/F19 11.9552 Tf 10.494 8.088 Td [(t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t i x T f x d x ; .5 cf.,Fig.6.1.Here T f isconstantoneachsubcell C j ,givenbyitsvalueattheregrid nodes. 77

PAGE 90

Whenthewholecell C isonrethatis, 0onallfourverticesof C t i is interpolatedalsolinearlytotheverticesofthesubcells C j .However,thecasewhen therelinecrossesthecell C requiresaspecialtreatmentoftheignitiontime t i ; t i x hasmeaningfulvalueonlywhenthenode x isonre, x 0.Also x =0and t i x = t onthereline.Thus,approximatingboth and t i inthereregionby linearfunctionssuggestsinterpolatingfromtherelation t i )]TJ/F19 11.9552 Tf 11.956 0 Td [(t = c; .6 forsome c .Weinterpolateonthegridlinesbetweentwonodesrst.Ifbothnodes areonre,weinterpolate t i bilinearlyasbefore.However,whenonecellcenterison reandonenot,say a 1 > 0, a 2 < 0,wendtheproportionalityconstant c in .6from t i a 2 = c a 2 ,andset t i b = c b atthemidpoint b = a 1 + a 2 = 2. Inthecaseofinterpolationtothenode c = a 1 + a 2 + a 3 + a 4 = 4betweennodes a 1 ; a 2 ; a 3 ; a 4 ,wendtheproportionalityconstant c bysolvingtheleastsquaresproblem 4 X j =1 a j 0 j t i a j )]TJ/F19 11.9552 Tf 11.955 0 Td [(t )]TJ/F19 11.9552 Tf 11.955 0 Td [(c a j j 2 min andsetagain t i c = c c 78

PAGE 91

Figure6.1:Divisionofremeshcellsintosubcellsforfuelfractioncomputation.The levelsetfunction andtheignitiontime t i aregivenatthecenters a 1 ;:::; a 4 ofthe cellsoftheregrid.Theintegral.5overthecell C withthecenter a 3 iscomputed asthesumofintegralsoverthesubcells C 1 ;:::;C 4 .Whilethevaluesof and t i are knownat a 3 = x 3 ,theyneedtobeinterpolatedtotheremainingcorners x 1 x 2 x 4 ofthesubcell C 1 fromtheirvaluesatthepoints a 1 ;:::; a 4 .Reproducedfrom[24]. 79

PAGE 92

Inordertocomputetheintegraloverasubcell C j ,werstneedtoestimatethe fractionofthesubcellthatisburning,by area f x 2 C j : x 0 g area C j = 1 2 1 )]TJ/F25 11.9552 Tf 16.471 17.116 Td [(P 4 k =1 x k P 4 k =1 j x k j ; .7 where x k arethecornersofthesubcell C j Next,replace t i x k by t when x k > 0i.e.,thenode x k isnotonre,and computetheapproximatefractionofthefuelburnedas 1 area C ZZ x 2 C x ;t 0 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(exp )]TJ/F19 11.9552 Tf 10.494 8.087 Td [(t )]TJ/F19 11.9552 Tf 11.955 0 Td [(t i x T f x d x 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(exp )]TJ/F15 11.9552 Tf 10.494 8.087 Td [(1 4 4 X k =1 t i x k )]TJ/F19 11.9552 Tf 11.955 0 Td [(t T f !! .8 6.2Conclusion Inthischapterweimplementthemethodofcomputingthefuelfractionofthecell thatispartiallyburning.Thisfuelfractioncalculation6.8isaccurateasymptotically whenthefuelburnsslowlyandtheapproximation oftheburningareaisexact.The estimation6.7oftheareaofthesubcellthatisburning,neededfor6.8,isexactwhen nopartofthesubcell C j ,isonrethatis,all x k 0andatleastone x k > 0; thewhole C j isonrethatis,all x k 0andatleastone x k < 0;thevalues x k denealinearfunctionandtherelinecrossesthesubcelldiagonallyorwhen itisalignedwithoneofthecoordinatedirections. 80

PAGE 93

REFERENCES [1]FrankA.AlbiniandElisabethD.Reinhardt.Modelingignitionandburningrate oflargewoodynaturalfuels. InternationalJournalofWildlandFire ,5:81{91, 1995. [2]HalE.Anderson.Aidstodeterminingfuelmodelsforestimatingrebehavior. USDAForestServiceGeneralTechnicalReportINT-122,1982. http://www. fs.fed.us/rm/pubs_int/int_gtr122.html [3]J.D.Beezley,A.Kochanski,V.Y.Kondratenko,J.Mandel,andB.Sousedk. SimulationoftheMeadowCreekreusingWRF-Fire.PosteratAGUFallMeeting2010,2010. http://www.openwfm.org/wiki/File:Agu10_jb.pdf ,retrieved December2011. [4]JonathanD.BeezleyandJanMandel.MorphingensembleKalmanlters. Tellus ,60A:131{140,2008. [5]GerritBurgers,PeterJanvanLeeuwen,andGeirEvensen.Analysisschemein theensembleKalmanlter. MonthlyWeatherReview ,126:1719{1724,1998. [6]T.L.Clark,M.A.Jenkins,J.L.Coen,andD.R.Packham.Acoupled atmosphere-remodel:RoleoftheconvectiveFroudenumberanddynamicngeringatthereline. InternationalJournalofWildlandFire ,6:177{190, 1996. [7]TerryL.Clark,JaniceCoen,andDonLatham.Descriptionofacoupled atmosphere-remodel. InternationalJournalofWildlandFire ,13:49{64,2004. [8]TerryL.Clark,MarryAnnJenkins,JaniceCoen,andDavidPackham.Acoupled atmospheric-remodel:Convectivefeedbackonrelinedynamics. J.Appl. Meteor ,35:875{901,1996. [9]J.L.Coen.SimulationoftheBigElkFireusingcoupledatmosphere-remodeling. InternationalJournalofWildlandFire ,14:49{59,2005. [10]JaniceCoenandNedPatton.Implementationofwildlandremodelcomponent intheWeatherResearchandForecastingWRFmodel. http://www.mmm. ucar.edu/research/wildfire/wrf/wrf_summary.html ,2010.VisitedDecember2010. [11]NoelA.C.Cressie. StatisticsforSpatialData .JohnWiley&SonsInc.,New York,1993. 81

PAGE 94

[12]JimyDudhia.TheWeatherResearchandForecastingmodel:2010annual update.2010WRFUsersWorkshop,2010. http://www.mmm.ucar.edu/wrf/ users/workshops/WS2010/abstracts/1-1.pdf [13]GeirEvensen. DataAssimilation:TheEnsembleKalmanFilter .Springer,2nd edition,2009. [14]MarkA.Finney.Firegrowthusingminimumtraveltimemethods. Canadian JournalofForestResearch ,32:1420{1424,2002. [15]ReinhardFurrerandThomasBengtsson.Estimationofhigh-dimensionalprior andposteriorcovariancematricesinKalmanltervariants. J.Multivariate Anal. ,98:227{255,2007. [16]P.Johnston,J.Kelso,andG.J.Milne.Ecientsimulationofwildrespreadon anirregulargrid. InternationalJournalofWildlandFire ,17:614{627,2008. [17]GeorgiJordanov,JonathanD.Beezley,NinaDobrinkova,AdamK.Kochanski, JanMandel,andBedrichSousedk.Simulationofthe2009HarmanlireBulgaria.InI.Lirkov,S.Margenov,andJ.Wansiewski,editors, 8thInternational ConferenceonLarge-ScaleScienticComputations,Sozopol,Bulgaria,June610,2011 ,volume7116of LectureNotesinComputerScience ,pages291{298. Springer,2012.AlsoavailableasarXiv:1106.4736. [18]EugeniaKalnay. AtmosphericModeling,DataAssimilationandPredictability CambridgeUniversityPress,2003. [19]A.K.Kochanski,M.A.Jenkins,S.K.Krueger,J.Mandel,andJ.D.Beezley. Realtimesimulationof2007SantaAnares. ForestEcologyandManagement 15:136{149,2013. [20]VolodymyrY.Kondratenko,JonathanD.Beezley,AdamK.Kochanski,andJan Mandel.IgnitionfromareperimeterinaWRFwildlandremodel.Paper 9.6,12thWRFUsers'Workshop,NationalCenterforAtmosphericResearch, June20-24,2011,2011. http://www.mmm.ucar.edu/wrf/users/workshops/ WS2011/WorkshopPapers.php ,retrievedAugust2011. [21]V.Mallet,D.E.Keyes,andF.E.Fendell.Modelingwildlandrepropagation withlevelsetmethods. Computers&MathematicswithApplications ,57:1089{ 1101,2009. [22]J.Mandel,S.Amram,J.D.Beezley,G.Kelman,A.K.Kochanski,V.Y.Kondratenko,B.H.Lynn,B.Regev,andM.Vejmelka.RecentadvancesandapplicationsofWRF-SFIRE. NaturalHazardsandEarthSystemScience ,14:2829{ 2845,2014. [23]JanMandel,JonathanD.Beezley,JaniceL.Coen,andMinjeongKim.Data assimilationforwildlandres:EnsembleKalmanltersincoupledatmospheresurfacemodels. IEEEControlSystemsMagazine ,29:47{65,June2009. 82

PAGE 95

[24]JanMandel,JonathanD.Beezley,andAdamK.Kochanski.Coupled atmosphere-wildlandremodelingwithWRF3.3andSFIRE2011. GeoscienticModelDevelopment ,4:591{610,2011. [25]JanMandel,JonathanD.Beezley,AdamK.Kochanski,VolodymyrY.Kondratenko,andMinjeongKim.Assimilationofperimeterdataandcouplingwith fuelmoistureinawildlandre{atmosphereDDDAS. ProcediaComputerScience ,9:1100{1109,2012.ProceedingsofICCS2012. [26]JanMandel,JonathanD.Beezley,andVolodymyrY.Kondratenko.FastFourier transformensembleKalmanlterwithapplicationtoacoupledatmospherewildlandremodel.InA.M.Gil-LafuenteandJ.M.Merigo,editors, ComputationalIntelligenceinBusinessandEconomics,ProceedingsofMS'10 ,pages 777{784.WorldScientic,2010.AvailableasarXiv:1001.1588. [27]JanMandel,JonathanD.Beezley,andVolodymyrY.Kondratenko.FastFourier transformensembleKalmanlterwithapplicationtoacoupledatmospherewildlandremodel.InA.M.Gil-LafuenteandJ.M.Merigo,editors, ComputationalIntelligenceinBusinessandEconomics,ProceedingsofMS'10 ,pages 777{784.WorldScientic,2010. [28]JanMandel,LorenCobb,andJonathanD.Beezley.Ontheconvergenceofthe ensembleKalmanlter.arXiv:0901.2951,January2009. [29]JanMandelandVaibhavKulkarni.Constructionofalevelfunctionforreline dataassimilation.CCMTechnicalReport234,UniversityofColoradoatDenver, June2006. http://ccm.ucdenver.edu/reports/rep234.pdf [30]J.Michalakes.RSL:Aparallelruntimesystemlibraryforregionalatmospheric modelswithnesting.InScottB.Baden,NikosP.Chrisochoides,DennisB. Gannon,andMichaelL.Norman,editors, StructuredAdaptiveMeshRenement SAMRGridMethods ,pages59{74.Springer,2000. [31]StanleyOsherandRonaldFedkiw. LevelSetMethodsandDynamicImplicit Surfaces .Springer,NewYork,2003. [32]EdwardG.PattonandJaniceL.Coen.WRF-Fire:Acoupledatmosphere-re moduleforWRF.In PreprintsofJointMM5/WeatherResearchandForecastingModelUsers'Workshop,Boulder,CO,June22{25 ,pages221{223. NCAR,2004. http://www.mmm.ucar.edu/mm5/workshop/ws04/Session9/ Patton_Edward.pdf ,retrievedDecember2011. [33]RonaldG.RehmandRandallJ.McDermott.Fire-frontpropagationusingthe levelsetmethod.NISTTechnicalNote1611,March2009. http://fire.nist. gov/bfrlpubs/fire09/art023.html [34]RichardC.Rothermel.Amathematicalmodelforpredictingrespreadin wildlandres.USDAForestServiceResearchPaperINT-115,1972. http: //www.treesearch.fs.fed.us/pubs/32533 83

PAGE 96

[35]J.A.Sethian. Levelsetmethodsandfastmarchingmethods ,volume3of CambridgeMonographsonAppliedandComputationalMathematics .CambridgeUniversityPress,Cambridge,secondedition,1999. [36]J.A.Sethian.Evolution,implementation,andapplicationoflevelsetandfast marchingmethodsforadvancingfronts. J.Comput.Phys. ,169:503{555,2001. [37]WilliamC.Skamarock,JosephB.Klemp,JimyDudhia,DavidO.Gill,DaleM. Barker,MichaelG.Duda,Xiang-YuHuang,WeiWang,andJordanG.Powers. AdescriptionoftheAdvancedResearchWRFversion3.NCARTechnicalNote 475,2008. http://www.mmm.ucar.edu/wrf/users/docs/arw_v3.pdf ,retrieved December2011. [38]A.L.Sullivan.Areviewofwildlandrespreadmodelling,1990-present,1: Physicalandquasi-physicalmodels,2:Empiricalandquasi-empiricalmodels, 3:Mathematicalanaloguesandsimulationmodels. InternationalJournalof WildlandFire ,18:1:347{368,2:369{386,3:387{403,2009. [39]WeiWang,CindyBruyere,MichaelDuda,JimyDudhia,DaveGill,Hui-Chuan Lin,JohnMichalakes,SyedRizvi,XinZhang,JonathanD.Beezley,JaniceL. Coen,andJanMandel.ARWversion3modelingsystemuser'sguide.Mesoscale &MiscroscaleMeteorologyDivision,NationalCenterforAtmosphericResearch,July2010. http://www.mmm.ucar.edu/wrf/users/docs/user_guide_ V3/ARWUsersGuideV3.pdf 84