\documentclass[12pt]{report}
\usepackage{geometry}
\geometry{a4paper, tmargin=3cm, bmargin=3cm, lmargin=3cm, rmargin=4cm}
\usepackage{algorithm}
\usepackage{xepersian}
\settextfont[Scale=1.2]{B Nazanin}
\setlatintextfont{Times New Roman}
\setdigitfont{Yas}
\begin{document}
همان طور که در مثال نیز مشاهده شد محاسبه ماتریس $\tilde{A}$ در هر تکرار، هم از لحاظ تعداد محاسبات و هم از لحاظ زمانی مقرون به صرفه نیست. بنابراین تضمین کارایی الگوریتم گفته شده در گرو امکان به کار بردن آن بدون نیاز به محاسبه تک تک درایه های ماتریس $\tilde{A}_i$ می باشد. یک راه حل برای این مشکل به این صورت است که اندیس های $t_i$ و $j_i$ را به گونه ای انتخاب کنیم که $\tilde{r}_{t_i}^i$ و $\tilde{c}_{j_i}^i$ و در نتیجه $(\tilde{r}_{t_i}^i-1)(\tilde{c}_{j_i}^i-1)$ به صورت قابل انتظاری کوچک باشند. از آنجا که طبق رابطه \ref{mar}، $t$امین سطر $\tilde{A}_i$، $a_t^TH_i^T$ است پس $\tilde{r}_t^i$ تعداد غیر صفرها در $a_t^TH_i^T$ می باشد. بنابراین اندیس سطر $t_i$ از ماتریس $A$ را به گونه ای انتخاب می کنیم که از بین تمام سطرهای ماتریس $A$ که تاکنون در نظر گرفته نشده دارای کمترین درایه غیر صفر باشد و قرار می دهیم $s_i=H_ia_{t_i}$. برای این کار کافی است قبل از شروع الگوریتم سطر های ماتریس $A$ را بر اساس تعداد درایه های غیر صفر به صورت صعودی مرتب کنیم. به طور مشابه از آنجا که $j$ امین ستون ماتریس $\tilde{A}_i$، $A_{m-i}h_j$ است $j_i$ را اندیس ستونی از ماتریس $\tilde{A}_i$ قرار می دهیم که از بین تمام درایه های غیر صفر بردار $s_i$ صادق در نامساوی \ref{mar}، متناظر با سطری از $H_i$ باشد که دارای کمترین تعداد ناصفر ها است. بنابراین با ترفند گفته شده نیاز به محاسبه ماتریس $\tilde{A}$ در هر مرحله از بین می رود.

ما برای توضیح ایده خود در ابتدا فرض کردیم ماتریس $A$ دارای رتبه سطری کامل باشد. با این وجود در الگوریتمی که در ادامه خواهیم گفت نیازی به این محدودیت نیست (اگر $s_i=0$، آنگاه سطر فعلی را رها کرده و سطر بعدی را در نظر خواهیم گرفت). انتظار می رود الگوریتم پیشنهاد شده بتواند یک پایه پوچ تنک برای ماتریس تنک تولید کند. شرح الگوریتم به صورت زیر می باشد.\\
 از آنجا که طبق رابطه \ref{mar}، $t$امین سطر $\tilde{A}_i$، $a_t^TH_i^T$ است پس $\tilde{r}_t^i$ تعداد غیر صفرها در $a_t^TH_i^T$ می باشد. بنابراین اندیس سطر $t_i$ از ماتریس $A$ را به گونه ای انتخاب می کنیم که از بین تمام سطرهای ماتریس $A$ که تاکنون در نظر گرفته نشده دارای کمترین درایه غیر صفر باشد و قرار می دهیم $s_i=H_ia_{t_i}$. برای این کار کافی است قبل از شروع الگوریتم سطر های ماتریس $A$ را بر اساس تعداد درایه های غیر صفر به صورت صعودی مرتب کنیم. به طور مشابه از آنجا که $j$ امین ستون ماتریس $\tilde{A}_i$، $A_{m-i}h_j$ است $j_i$ را اندیس ستونی از ماتریس $\tilde{A}_i$ قرار می دهیم که از بین تمام درایه های غیر صفر بردار $s_i$ صادق در نامساوی \ref{mar}، متناظر با سطری از $H_i$ باشد که دارای کمترین تعداد ناصفر ها است. بنابراین با ترفند گفته شده نیاز به محاسبه ماتریس $\tilde{A}$ در هر مرحله از بین می رود.

ما برای توضیح ایده خود در ابتدا فرض کردیم ماتریس $A$ دارای رتبه سطری کامل باشد. با این وجود در الگوریتمی که در ادامه خواهیم گفت نیازی به این محدودیت نیست (اگر $s_i=0$، آنگاه سطر فعلی را رها کرده و سطر بعدی را در نظر خواهیم گرفت). انتظار می رود الگوریتم پیشنهاد شده بتواند یک پایه پوچ تنک برای ماتریس تنک تولید کند. شرح الگوریتم به صورت زیر می باشد.\\




\begin{algorithm}[H]
\caption{الگوریتم ...برای محاسبه یک پایه پوچ تنک}\label{alg2}

\textbf{مرحله 1.} سطرهای ماتریس $A \in R^{m,n}$ را بر اساس تعداد درایه های غیر صفر به صورت صعودی مرتب کرده و آنها را به ترتیب $a_{t_1}$ تا $a_{t_m}$ بنامید. همچنین فرض کنید $H_1$ ماتریس همانی در $R^{n,n}$ و $u \in [0 1]$ یک عدد ثابت باشد. قرار دهید $r_1=n$ و $i=1$.\\
\textbf{مرحله 2.} قرار دهید $s_i=H_ia_{t_i}$. \\
\textbf{مرحله 3.} اگر $s_i=0$ قرار دهید $r_{i+1}=r_i$، $i=i+1$، $H_{i+1}=H_i$ و به گام دوم بروید.\\
\textbf{مرحله4.} فرض کنید $s_i^{j_i}$ درایه ی غیر صفری از $s_i$ باشد که از بین همه درایه های غیر صفر $s_i$ صادق در نامساوی 
\[ |s_i^{j_i}| \geq u \max \{|s_i^k|, 1 \leq k \leq n-i+1 \}, \] 
متناظر با سطری از $H_i$ باشد که دارای کمترین تعداد عناصر غیر صفر است(در صورتی که  کمینه روی چند اندیس رخ دهد اولین را انتخاب کنید).\\
\textbf{مرحله 5.} $s_i$ و $G_i$ را به صورت گفته شده در نظر بگیرید و قرار دهید $H_{i+1}=G_iH_i$.\\
\textbf{مرحله 6.} اگر $i=m$، متوقف شوید ($H_{m+1}$ یک پایه ی پوچ برای فضای پوچ ماتریس $A$ است). در غیر این صورت قرار دهید $r_{i+1}=r_i-1$، $i=i+1$ و به گام دوم بروید.
\end{algorithm}
\end{document}