# FastSweepMethod

**Repository Path**: jedi-knight/fast-sweep-method

## Basic Information

- **Project Name**: FastSweepMethod
- **Description**: 求解程函方程的快速扫描法(fast sweep method)
- **Primary Language**: C++
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-11-29
- **Last Updated**: 2024-09-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 快速扫描法
快速扫描法FSM是求解程函方程的高效算法，广泛应用于地质学，其思想是使用Godnov一阶迎风格式对程函方程进行离散，得到一个二次方程组。使用G-S迭代法对这个方程组求解。可以证明，沿着不同方向进行有限次扫描之后，解一定会收敛。所以算法的时间复杂度是O(N)。

本程序实现了二维的FSM方法，其中FSM基类实现了FSM方法，Burnback类派生自FSM，是FSM在固体火箭发动机装药中的实际应用，实现了装药燃面面积的计算。

为了提高计算速度，引入LOCK规则，标记每个节点是否处于锁定状态。对于那些已经计算出时间场或不能计算时间场的节点上锁。这些锁定的节点在G-S迭代中不做计算，以减少不必要的计算量。
## 1 使用案例
``` c++
#include <iostream>
#include <math.h>
#include <vector>
#include <time.h>

#include "burnBack.h"

int main()
{
    // example 1: FSM基类测试，对于200*200正方形求解区域完成快速扫描，得到解
    {
        const int nx = 200, ny = 200;
        FSM fsm(nx, ny, 1);
        fsm.sweep(5);
        fsm.outputU("u_exp1.dat");
        fsm.outputLock();
    }

    // example 2: FSM的派生类BurnBack测试,针对二维固体装药实现燃面推移，得到燃面面积随时间变化曲线
    {
        //对于二维固体火箭发动机装药，计算区域限制在半径为R，角度theta的扇形内
        const double R = 1.0, theta = 60.0;
        const int nx = 200;
        const double h = 1.1 * R / nx;
        const int ny = nx * sin(theta * M_PI / 180.0);

        BurnBack burnBack(theta, R, nx, ny, h);
        burnBack.sweep(5);
        burnBack.outputAera();
        burnBack.outputU("u_exp2.dat");
        burnBack.outputUSteps();
        burnBack.outputLock("lock_exp2.dat");
    }

    // example 3: 计算速度测试，重复100次二维固体装药实现燃面推移
    {
        const double R = 1.0, theta = 60.0;
        const int nx = 200;
        const double h = 1.1 * R / nx;
        const int ny = nx * sin(theta * M_PI / 180.0);

        BurnBack burnBack(theta, R, nx, ny, h);

        clock_t start = clock();
        for (int i = 0; i < 100; i++)
        {
            burnBack.sweep(5);
            burnBack.calAera();
        }
        clock_t end = clock();
        std::cout << "平均每次计算用时t:" << (end - start) / 1000.0 / 100.0 << " ms" << std::endl;
        std::cout << "t/N:" << 1000 * (end - start) / 100.0 / (nx * ny) << " ns/节点" << std::endl;
    }
    return 0;
}

```
## 2 效果
典型2D管槽型装药的燃面推移
![avatar](./doc/result.png)
在特定网格下，每次计算耗时1ms。时间复杂度是O(N),也即是每增加一个节点，耗时增加30 ns。
这对大规模优化设计提供了有力支撑。以1ms为例，如果某个优化设计问题需要进行10万次计算，那么总耗时可以控制在100秒以内。考虑到可以使用48个核心完成并行优化计算，**那么总耗时可以控制在2秒左右，实现真正意义上的实时装药优化设计**！
## 参考文献

[1] Zhao, Hongkai. “A fast sweeping method for Eikonal equations.” Math. Comput. 74 (2005): 603-627.[[PDF]](https://www.ams.org/journals/mcom/2005-74-250/S0025-5718-04-01678-3/S0025-5718-04-01678-3.pdf)

[2] McLaughlin, Joyce and Renzi, Daniel. "Some Improvements for the Fast Sweeping Method." SIAM J. Sci. Comput. 32 (2010): 2853-2874[[PDF]](https://epubs.siam.org/doi/abs/10.1137/090749645)